如何撤消链表 - 详细解释

Question

任何人都可以共享代码的链接，解释如何反转linked list?或者有人可以解释下面的代码片段吗？

我试图绘制/写入它，但仍然没有得到节点如何反转。

public void reverseList() {
   Node reversedPart = null;
   Node current = head;
   while (current != null) {
       Node next = current.next;
       current.next = reversedPart;
       reversedPart = current;
       current = next;
   }
   head = reversedPart;
}

Answer 1

我们来看一个简单的例子：

1 > 2 > 3 > 4 > 5 > null - our list

Before the while(...) loop: node = 1, head = null

While moving over the list:

1 step:                 1 > null; node = 1, head = null, node.next = head, head = node

2 step:             2 > 1 > null; node = 2, head = 1,    node.next = head, head = node

3 step:         3 > 2 > 1 > null; node = 3, head = 2,    node.next = head, head = node

4 step:     4 > 3 > 2 > 1 > null; node = 4, head = 3,    node.next = head, head = node

5 step: 5 > 4 > 3 > 2 > 1 > null; node = 5, head = 4,    node.next = head, head = node

注释代表算法的第一步：

public Node reverseList(Node head) {
    Node focusNode = head;          // focusNode = 1
    head = null;                    // no comments...
    while (focusNode != null) {
      Node parent = focusNode;      // parent = 1
      focusNode = focusNode.next;   // focusNode = 2; moving over the list...
      parent.next = head;           // parent.next = null (1 -> null)
      head = parent;                // head = 1
    }
    return head;
}

Answer 2

首先，应该在while循环中避免使用Node next以消除任何混淆。您最好将next重命名为nodeNext，并在while循环之外声明Node nodeNext，并使用nodeNext = current.next;来排除任何混淆。我认为那是你混乱的根源。

这段代码正在做的是它正在颠倒每个节点的链接方向。

每个节点的下一个节点方向正在反转。第一节点指向第二节点（最初指向第一节点的节点）的方向被反转，第一节点指向其前任，并且前面的节点指向第一节点。

这一直持续到最后一个节点，即current!=null。之后，只要当前变为空，循环就不再进行迭代，并且所有元素都已反转。