如何反转链表？

algorithm data-structures java linked-list singly-linked-list

2022-09-01 21:40:10

考虑：

 Node reverse(Node head) {
    Node previous = null;
    Node current = head;
    Node forward;

    while (current != null) {
        forward = current.next;
        current.next = previous;
        previous = current;
        current = forward;
    }

    return previous;
}

它究竟是如何逆转列表的？

我得到它首先将第二个节点设置为。然后它说等于一个节点。然后它说是现在。最后变成？forwardcurrent.nextnullpreviouspreviouscurrentcurrentforward

我似乎无法理解这一点以及它是如何逆转的。有人可以解释一下这是如何运作的吗？

答案 1

enter image description here

答案 2

您可以迭代地反转列表，并始终将间隔 [head， previous] 中的列表正确反转（因此当前是第一个未正确设置其链接的节点）。在每个步骤中，您执行以下操作：

您记住当前节点的下一个节点，以便您可以从它继续
您将当前链接设置为指向上一个，如果您考虑一下，这是正确的方向
您将以前的链接更改为当前，因为现在当前也已正确设置其链接
将未正确设置其链接的第一个节点更改为第一步中记住的节点

如果对所有节点执行此操作，则可以证明（例如使用归纳法）列表将被正确反转。