#data-structures #linked-list
#структуры данных #связанный список
Вопрос:
извините за неудобный заголовок вопроса. Я действительно не знаю, как объяснить без примера кода. Я реализовал связанный список с использованием дженериков, и я пытаюсь его изменить.
public Node<T> reverse() {
Node<T> prev = null;
while (head != null) {
Node<T> next = head.next;
head.next = prev;
prev = head;
head = next;
System.out.println("head: " head.next "nprev: " prev.next);
}
head = prev;
return prev;
}
head = prev;
Мой вопрос в том, зачем это требуется?
Мои выходные данные LinkedList: [вывод]
Но без head = prev; строки он просто выводит пустой [] . Это как-то связано с дженериками?
Ответ №1:
Нет, это не имеет ничего общего с generics тем, что, глядя на ваш обратный метод, изначально есть три узла prev , указывающие на null, head указывающие на начало связанного списка и next указывающие на head следующий узел. На каждом шаге вы перемещаете каждый узел в прямом направлении, пока он не будет перевернут, поэтому после завершения ваш prev узел будет указывать на хвост связанного списка, который на самом деле является началом перевернутого связанного списка, и оба head и next указывают на null . So head = prev необходимо, чтобы head указать начальный узел перевернутого связанного списка.
Комментарии:
1. Привет. спасибо, что нашли время для ответа. Моя главная проблема заключается в том, что у меня, похоже, нет этой проблемы, если я не включу ее в эту версию: leetcode.com/submissions/detail/597095512 Почему вышеприведенная версия работает, а моя — нет? Имейте в виду, что я конкретно имею в виду пропуск части ‘head = prev’. На мой взгляд, они точно такие же; если я не включу строку перед возвратом, то есть.
2. Ссылка разорвана
3. Упс! Попробуйте это: pastebin.com/HxPJ4KgR
4. В этой версии возвращаемое значение является правильным узлом
prev, который в вашей версии такжеprevявляется правильным возвращаемым узлом, ноheadузел является глобальным. Итак, вам необходимо либо назначитьhead = prev, либоhead = reverse()5. Ах, так это, по сути, проблема с областью видимости? Т.Е., Если бы я создал ‘Node head’ в paretheses параметров, это исправило бы это? Это имело бы смысл, поскольку я на самом деле удалил это специально, поскольку я просто хотел назвать это как ‘list.reverse ()’.
Ответ №2:
* TLDR; Потому что в конце цикла while ‘head’ указывает на null, а не на перевернутый список.
—
Давайте разберемся с вашим кодом на примере: Список: 3 -> 6 -> 9 -> нулевой заголовок указывает на 3. // 1
Node<T> prev = null;
while(head != null) // true
Node<T> next = head.next; // next -> 6, as head.next points to Node with element 6
head.next = prev; // head->next = null, earlier it pointed to Node with element 6, prev is null
prev = head;
head = next;
Текущее состояние:
null <- 3 6 -> 9 -> null
Now, prev points to 3, head points to 6.
// 2
while(head != null) // true
Node<T> next = head.next; // next -> 9, as head.next points to Node with element 9
head.next = prev; // head->next =3, earlier it pointed to Node with element 9, prev is 3
prev = head;
head = next;
Текущее состояние:
null <- 3 <- 6 9 -> null
Now, prev points to 6, head points to 9.
// 3
while(head != null) // true
Node<T> next = head.next; // next -> null, as head.next points to null
head.next = prev; // head->next =6, earlier it pointed to null, prev is 6
prev = head;
head = next;
Текущее состояние:
null <- 3 <- 6 <- 9
Now, prev points to 9, head points to null.
// 4
while(head != null) // false
Now, head points to null and you need to return reversed linked list.
head = prev; // prev points to the node with element 9.
// null <- 3 <- 6 <- 9 <- prev (or head) as head and prev are equal.
return prev; // will return the reversed linked list.
return head; // will return the reversed linked list as both prev and head are equal.