刷题总结——链表
总论
- 链表提供快速的前后访问和插入，不提供随机访问，要是需要随机访问需要结合hash实现
- 链表反转类问题的关键是3个节点
prev curr next之间的关系：- 由于反转的时候next会被改变，因此需要临时存储设置next的tmp = cur->next; 之后可以反转，再更新prev和curr即可
- dummy node的引入，是为了简化与头节点有关的操作，由于头节点可能发生变化，通过dummy获得返回值方便
- 链表删除问题不一定要真正的删除，只需要其不出现在原来的链上即可
链表反转
- 头插法
- 反转k个
- 需要注意的是插入dummy节点，用来构成p0
- 核心的链接逻辑
p0->next->next = cur; // reversed k-list tail
p0->next = pre; // reversed k-list head
- k个一组反转
- 需要注意先求出需要多少个k组反转（链表总长度）
- 理解p0的含义，p0是每组开始前的pre记录，不会随着pre更新，但是每组结束之后需要更新一下
- 因此需要在每次k个翻转结束之后，进行p0更新，开始之前记录下一个p0的位置
链表快慢指针
寻找节点
- 找中间节点，同时出发，按照速度1:2移动
- 环形链表找入口：Floyd算法，按照速度1:2移动，快慢必会相遇，之后调节其中一个至起始点，按照速度1:1移动
- 链表重排，快慢链表找中点+反转链表
删除节点
- 删除第n个
- 删除倒数第n(快慢)
- 去除重复元素(快慢)
MISC
- 2个链表交点问题：方法1: 前后相接/方法2: 先求各自长度之后移动
- LRU问题：设计双向链表+哈希表索引key到链表地址，注意双向链表初始化的方式
- 使用dummy node的prev来保证LRU删除的最后一个节点
- 实现hash存储：使用拉链法解决hash冲突
- 链表实现大数加法计算：2个链表注意进位
- 链表归并排序：使用堆辅助实现
- 两两交换链表节点：注意交换的方法，下一次交换开始前要设置好prev的位置，不妨多用几个临时变量来表示中间值
- 加一个默认的dummy节点，返回dummy->next
参考资料
- 灵神题单：https://leetcode.cn/circle/discuss/K0n2gO/