发布于

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

题目如下

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

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

二叉搜索树心得

什么是二叉树？

  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（字典树、前缀树）（多叉树）（对字符串的操作）