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

题目如下

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


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

二叉搜索树心得

什么是二叉树?

  1. 二叉树像链表一样,属于动态数据结构
  2. 二叉树的特点:
    1. 二叉树具有唯一的根节点
    2. 二叉树的每一个节点最多只有两个孩子
  3. 二叉树具有天然的递归结构
    1. 每一个节点的左、右子树也是一个二叉树
  4. 二叉树不一定是满的

二叉树的节点

//节点
type Node struct{
    value  int      //节点值
    Node   *left        //左孩子
    Node   *right   //右孩子
}

//二叉树
type BST struct{
    Node root   //根节点
    int  size   //二叉树的节点数(大小)
}

为什么要发明这种树结构?

  1. 树结构本身是一种天然的组织结构。
  2. 树结构具有高效性。

二分搜索树的应用举例

  • 平衡二叉树
  • AVL
  • 红黑树
  • 堆、并查集
  • 线段树
  • Trie(字典树、前缀树)(多叉树)(对字符串的操作)