为什么我需要使 'head' 等于 'prev' 才能完成反转链表？

Question

抱歉这个尴尬的问题标题。如果没有代码示例，我真的不知道如何解释。我已经使用泛型实现了一个链表，我正在尝试反转它。

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;

我的问题是，为什么需要这样做？

我的链表输出： [输出]

但如果没有 head = prev; 行，它只会输出空白 []。这与泛型有关吗？

Answer 1

不是，跟generics没有关系，看你的reverse方法，一开始有3个节点prev指向null，head指向链表，next指向head的下一个节点。在每一步你都在向前移动每个节点直到它被反转，所以完成后，你的 prev 节点将指向链表的尾部，这实际上是反向链表的开始，并且两者head 和 next 指向 null。所以需要head = prev才能使head指向反向链表的起始节点

Answer 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.

为什么我需要使 'head' 等于 'prev' 才能完成反转链表？

Why do I need to make 'head' equal to 'prev' to finish reversing a Linked List?

linked-list

data-structures