Удалить последний узел связанного списка.Каждый узел также имеет указатель данных, который указывает на некоторые данные

Question

Привет всем Я видел этот вопрос на сайте, заданном в техническом интервью

Узел имеет указатель данных и указатель на некоторые данные.

Может ли кто-нибудь помочь мне понять, что этот вопрос означает в деталях ??

Означает ли это, что узел имеет указатель на другой узел и также указывает на какой-то другой узел данных. И этот узел данных не указывает ни на какой другой узел. В этом случае наш узел будет иметь два указателя.

Я действительно смущен. Пожалуйста, помогите.

Заранее спасибо

Answer 1

Структура узла вашего списка довольно ясна. В C это будет выглядеть примерно так:

typedef struct list list;
struct list {
        list *next;
        void *data;
}

Однако, если ваша задача состоит в том, чтобы удалить последний узел связанного списка, эта задача неоднозначна. В отдельных связанных списках вы обычно вставляете новые узлы спереди, потому что это может быть выполнено за постоянное время. Таким образом, остается неясным, относится ли «последний узел» к узлу, который был вставлен совсем недавно (и, следовательно, является передним узлом), или относится ли он к первому вставленному узлу (и, следовательно, является последним узлом, который вы увидите, когда вы пройти через список).

В первом случае действительно легко удалить «последний» узел списка list, потому что это передний узел: list = list->next. Вы можете включить крайний случай пустого списка: list = list?list->next:NULL.

Во втором случае, когда вы должны удалить узел, который был вставлен первым, это немного сложнее. Вы должны пройти через список, поддерживая указатель на текущий элемент и, кроме того, указатель на элемент перед этим. Вот некоторый код, который вам может пригодиться:

cur = list->next;
prev = list;

while (cur->next != NULL) {
        prev = cur;
        cur = cur->next;
}

prev->next = NULL;

free(cur->data);
free(cur);

Этот код выполняет итерацию по списку и останавливается, когда cur указывает на последний узел (единственный узел списка, чей следующий указатель указывает на NULL). Затем мы отсоединяем последний узел, устанавливая следующий указатель предыдущего элемента в NULL.

Обратите внимание, что у вас есть два особых случая:
- список изначально пуст (тут ничего не поделаешь)
- список содержит только один элемент (т. е. первый элемент является последним элементом, переключитесь на метод, описанный ранее)

Answer 2

Представление связанного списка: [data1, p1]->[data2, p2]->[data3, p3] (p3 указывает на ничто)

Можно ожидать, что вы удалите data3, p3 и AND для p2, чтобы у вас не было потерянного указателя!

Answer 3

В идеале он должен читаться: у узла есть указатель «Next», а сами данные узла являются указателем.Подобные структуры данных распространены там, где сами данные могут быть огромными и не могут храниться в памяти или в пределах одного и того же узла.

Редактировать:

Просмотр ссылки на вопрос: мое предположение упомянутовыше, кажется, что это такое.Все, что вам нужно сделать, это взять указатель из поля данных узла и удалить этот до удаления узла.

Answer 4

Может быть, это немного прояснит для вас: http://en.wikipedia.org/wiki/Linked_list

Каждый узел в связанном списке имеет указатель на следующий узел и некоторые данные. Данные никогда не являются указателями на узлы в одном списке.

редактировать: Получив список, вы должны написать функцию, которая удаляет последний узел и гарантирует, что новый последний узел указывает на NULL.