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

题目如下

  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 = nilcur不能作为结果返回给被调用的函数


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

发表评论

电子邮件地址不会被公开。必填项已用 * 标注