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

题目如下

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


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

深入探讨 Go 多变量赋值

使用go语言时,会经常把一些变量放在同一行来声明、赋值或计算。那么,这种赋值方法到底是以什么样的实现方法来赋值的呢?

先说结论,就两步:
一、先计算等号右侧所有表达式的值,将结果存储临时变量中。
二、将临时变量的值赋给等式左侧的变量。

多个变量一同声明并赋值

a, b := 1, 5        //情况一
c, d := a+b, a-b    //情况二

对于情况一来说,很简单,直接按照从左到右的顺序,把1、2两个值赋值给a、b

  ; -----情况一  相关汇编代码  开始----------
  (.\main.go:4)     MOVQ    1, "".a+24(SP)             ; 将1赋值给a
  (.\main.go:4)     MOVQ5, "".b+16(SP)           ; 将5赋值给b
  ; -----情况一  相关汇编代码  结束----------

对于情况二来说,赋值的过程是这样的:
1. 计算a+b、a-b的值,并存储在两个临时变量中
2. 将运算结果从临时变量中调出来,从左到右依次赋给c, d两个变量。

  ; -----情况二  相关汇编代码  开始----------
  (.\main.go:5)     MOVQ    "".a+24(SP), AX           ; 将a赋值给AX寄存器
  (.\main.go:5)     ADDQ    $5, AX                    ; 将5和AX寄存器里的值相加(结果还保存在AX寄存器里)
  (.\main.go:5)     MOVQ    AX, ""..autotmp_4+56(SP)  ; 将AX寄存器里的值赋值给autotmp_4变量
  (.\main.go:5)     MOVQ    "".a+24(SP), AX           ; 将a赋值给AX寄存器
  (.\main.go:5)     SUBQ    "".b+16(SP), AX           ; 用AX里的值,减去b的值
  (.\main.go:5)     MOVQ    AX, ""..autotmp_5+48(SP)  ; 将AX里的计算结果赋值给autotmp_5变量
  (.\main.go:5)     MOVQ    ""..autotmp_4+56(SP), AX  ; 将autotmp_4变量放入AX寄存器中
  (.\main.go:5)     MOVQ    AX, "".c+8(SP)            ; 将AX寄存器中的值赋给c
  (.\main.go:5)     MOVQ    ""..autotmp_5+48(SP), AX  ; 将autotmp_5变量放入AX寄存器中
  (.\main.go:5)     MOVQ    AX, "".d(SP)              ; 将AX寄存器中的值赋给d
  ; -----情况二  相关汇编代码  结束----------

多个变量一同计算、互换变量值

func main() {
    a, b := 1, 5            //定义a, b
    c, d := a+b, a-b        //定义c ,d = 6, -4
    b, c, d = c, b, b+c     //探究单行多赋值计算
    _ = d                   //在本探究中没啥用的空行
}

对情况三来说,赋值的结果实际上是跟情况二是一样的:
1. 计算c、b、b+c的值(前两个无需计算),并存储在两个临时变量中(解释:为什么不是三个临时变量)
2. 将运算结果从临时变量中调出来,从左到右依次赋给b, c, d三个变量。

为什么不是三个临时变量?
对于前半部分 b, c = c, b ,想达成互换两个的值,只需要一个临时变量即可
temp := b
b = c
c = temp

  ; -----情况三  相关汇编代码  开始----------
  (.\main.go:6)     MOVQ    "".b+16(SP), AX           ; 将b的值,放入AX寄存器
  (.\main.go:6)     ADDQ    "".c+8(SP), AX            ; AX中的值加c的值(结果还保存在AX寄存器里)
  (.\main.go:6)     MOVQ    AX, ""..autotmp_6+40(SP)  ; 把上述计算结果赋值给autotmp_6变量
  (.\main.go:6)     MOVQ    "".b+16(SP), AX           ; 将b的值赋给AX
  (.\main.go:6)     MOVQ    AX, ""..autotmp_7+32(SP)  ; 把AX的值赋给autotmp_7变量
  (.\main.go:6)     MOVQ    "".c+8(SP), AX            ; 将c的值赋给AX
  (.\main.go:6)     MOVQ    AX, "".b+16(SP)           ; 把AX的值(c)赋给b
  (.\main.go:6)     MOVQ    ""..autotmp_7+32(SP), AX  ; 把autotmp_7变量的值赋给AX
  (.\main.go:6)     MOVQ    AX, "".c+8(SP)            ; 把AX的值(autotmp_7)赋给c
  (.\main.go:6)     MOVQ    ""..autotmp_6+40(SP), AX  ; 把autotmp_6变量的值赋给AX
  (.\main.go:6)     MOVQ    AX, "".d(SP)              ; 把AX的值(autotmp_6)赋给d
  ; -----情况三  相关汇编代码  结束----------

汇编代码详解:

实际应用(算法题)

《五行解决反转链表问题》


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