数据结构与算法之美笔记05（链表）

技巧一：理解指针或引用的含义

将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

技巧二：警惕指针丢失和内存泄漏

我们希望在结点a和相邻的结点b之间插入结点x，假设当前指针p指向结点a。如果我们将代码实现变成下面这个样子，就会发生指针丢失和内存泄露。

p->next = x;  // 将p的next指针指向x结点；
x->next = p->next;  // 将x的结点的next指针指向b结点；

插入结点时，一定要注意操作的顺序，要先将结点x的next指针指向结点b，再把结点a的next指针指向结点x，这样才不会丢失指针，导致内存泄漏。

同理，删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。

技巧三：利用哨兵简化实现难度

单链表的插入和删除操作。如果我们在结点p后面插入一个新的结点，

new_node->next = p->next;
p->next = new_node;

当我们要向一个空链表中插入第一个结点，刚刚的逻辑就不能用了。我们需要进行下面这样的特殊处理，其中head表示链表的头结点。所以，从这段代码，我们可以发现，对于单链表的插入操作，第一个结点和其他结点的插入逻辑是不一样的。

if (head == null) {
  head = new_node;
}

我们再来看单链表结点删除操作。如果要删除结点p的后继结点，

p->next = p->next->next;

但是，如果我们要删除链表中的最后一个结点，

if (head->next == null) {
   head = null;
}

技巧四：重点留意边界条件处理

我经常用来检查链表代码是否正确的边界条件有这样几个：

• 如果链表为空时，代码是否能正常工作？

• 如果链表只包含一个结点时，代码是否能正常工作？

• 如果链表只包含两个结点时，代码是否能正常工作？

• 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？

技巧五：举例画图，辅助思考

技巧六：多写多练，没有捷径

精选题目

• 单链表反转

• 链表中环的检测

• 两个有序的链表合并

• 删除链表倒数第n个结点

• 求链表的中间结点