链表

链表知识总结

如何写好链表代码

理解指针或引用的含义

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

警惕指针丢失和内存泄漏

插入结点时，一定要注意操作的顺序

往单链表中P结点后插入新结点x时，如果像下面这样写就会造成指针丢失。

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

正确方式应该是颠倒两个语句的顺序：

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

利用哨兵简化实现难度

普通链表插入和删除需要针对第一个结点或者最后一个结点进行单独处理， 使用带头的结点(不存储数据)可以将操作统一，代码更简洁。

重点留意边界条件

• 链表为空

• 链表只有一个结点

• 链表只有两个结点

• 头结点和尾结点处理

  举例画图，辅助思考

  通过举例和画图的方式，理清思路。

多写多练，没有捷径

Practice,Practice,Practice!

常见链表题目

快慢指针的思想很重要。

• 单链表反转

• 链表中环的检测

• 两个有序链表合并

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

• 求链表中间结点