发布于

五行解决反转链表问题 以及其引伸

题目如下

  1. 反转链表

反转一个单链表。
示例:
　　输入: 1->2->3->4->5->NULL
　　输出: 5->4->3->2->1->NULL
进阶:
　　你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

力扣206题，传送门

解法：

func reverseList(head *ListNode) *ListNode {
    cur := head        //当前节点
    var prev *ListNode //前一个节点（”第一个“前一个节点为nil）
    for cur != nil {
        cur.Next, prev, cur = prev, cur, cur.Next
    }
    return prev
}

没错，就是这么简单XD。

解法详解：

2、3行，定义变量就不用说了。
4行，当当前节点不为空的时候，进行循环。

重点 第5行：该行完成了翻转、指针移动的这两个关键步骤。

使用了连等式（多值赋值）。在这一行，看样子像是给三个变量进行更新赋值，实则它还隐藏着三个临时变量。
这里就需要先了解一下 多值赋值 的运算过程了：
　　多值赋值会在当前变量所拥有的值的基础上，先计算等号右侧表达式的各个值，并在必要的情况下存储在临时变量中。再将右侧表达式的各个值，依次赋给等号左侧的变量（顺序为从左到右）。

详细分析多变量的赋值，请看这篇文章→《深入探讨Go多变量赋值》

  1. 先计算（备份）变量的值 到 临时变量中
    即：先备份当前的 prev, cur，记作 Temp_prev, Temp_cur
    计算当前的 cur.Next，存入 Temp_cur_Next中。
  2. 再对节点进行翻倒（赋值）
    cur.Next = Temp_prev　　//将 当前节点的后继指针 指向 前一个节点。（完成翻转）
    prev = Temp_cur　　　　//将 前一个节点 定义为 当前节点。（完成前一个节点指针的移动）
    cur = Temp_cur_Next　　//将 当前节点 定义为 旧的“当前节点”的下一个节点。（完成当前节点指针的移动）

次重点 第7行：返回的结果为什么是prev（前一个节点），而不是cur（当前节点）？

在 最后一个节点 进行计算前，链表是这样的，1 <- 2 <- 3 <- 4 5 -> nil

  1. 计算后，赋值前的情况（计算了等号右侧的变量值，并存储在了临时变量里，还没有给等号左侧的变量修改值的时候）：
    此时：prev = 4; cur = 5; Temp_prev = 4; Temp_cur = 5; Temp_cur_Next = nil;

  2. 计算后，开始对等号左侧的变量进行赋值（开始修改等号左侧变量的时候）：
    备注：括号中的值代表的指针当前指向的元素
    cur.Next(5.Next) = prev(4)　　//完成了最后两个元素的翻转
    prev = Temp_cur(5)　　　　　//即：翻转后得到的新链表的 head
    cur = Temp_cur_Next(nil)　　//达到 for解除循环的临界条件：cur = nil

显然，cur = nil，cur不能作为结果返回给被调用的函数

作者能力有限，若有哪些地方有误，请在评论区里指正。愿我们一同进步！