一行反转LinkedList

Question

我刚刚在 LeetCode 上使用 Go 中的一行找到了反向链表的解决方案。它确实有效，但我不明白如何实现。

就是这样：

func reverseList(head *ListNode) (prev *ListNode) {
    for head != nil {
        prev, head, head.Next = head, head.Next, prev 
    }
    
    return
}

例如让列表为

[1->2->3->4->5->nil]

。

我知道它的工作原理如下：

1. 首先去执行

   head.Next = prev

   （

   head.Next = nil

   ，所以现在

   head = [1->nil]

   ）

2. 然后，

   prev = head

   （在这一步

   prev = [1->nil]

   就像上一步中的

   head

   ）

3. head = head.Next

   并且有魔法。对于第二步中的

   prev

   ，使用

   head = [1->nil]

   ，但是在这一步之后

   head = [2->3->4->5->nil]

因此，当

head != nil

进行迭代时，在第二步

prev = [2->1->nil]

、

head = [3->4->5->nil]

等等。

这条线可以表示为：

for head != nil {
        a := *head
        prev, a.Next = &a, prev
        head = head.Next
    }

我说得对吗？为什么会这样？

Answer 1

表达式左侧的变量，被赋给当时表达式右侧的值。这是语言的巧妙运用。

为了更容易理解，我们来看一个例子。

设置

这是我们的链接列表：
1 -> 2 -> 3 -> 4 -> 无

在函数执行之前，

• 头是*节点1
• prev 为零（未初始化）
• head.下一个是*节点 2

一步一步

prev, head, head.Next = head, head.Next, prev

让我们分解一下，

• prev (nil) = head (*节点 1)
• head (*节点 1) = head.Next (*节点 2)
• head.Next (*节点 2) = prev (nil)

下一次迭代，

• prev (*节点 1) = head (*节点 2)
• head (*节点 2) = head.Next (*节点 3)
• head.Next (*节点 3) = prev (*节点 1)

总结

基本上，它将

head.Next

反转到前一个节点，并将 prev 和 head 移动到下一个节点。

将其与 Go 中的教科书算法进行比较就清楚了：

func reverseList(head *ListNode) *ListNode {
    var prev *ListNode

    for head != nil {
        nextTemp := head.Next
        head.Next = prev
        prev = head
        head = nextTemp
    }

    return prev
}