链表LinkedList是一种线性的非连续数据结构,优势是随机删除和添加特别高效,但随机访问效率差。因为链表边界条件较多,容易出错,所以还是比较常见的一类题目。但链表常见的问题就那么多,总结起来就那么几个,想要掌握还是比较容易的。
单链表
单链表是出现频率最高的,虽然现实中很少用它,因为它的效率差,现实中一般多用双向链表。单链表也即是每个节点只有一个指针,指向下一个节点,只能从前往后的顺序来遍历,如果想对某一个节点进行操作,必须找到这个节点的前一个节点。
哨兵节点
哨兵节点是指在输入的头节点的前面加一个节点,它的值没有任何意义,它的存在是为了简化逻辑。通常用于添加和删除操作中,如果输入的头节点是null,那么就需要特殊处理,而用了哨兵节点,就可以简化逻辑。
比如说,常规的添加和删除:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
|
可以看到为了处理头节点是null的情况要加很多逻辑,但如果使用哨兵节点,逻辑就会非常简单:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
哨兵节点的作用是要能简化逻辑,一般用在需要考虑头节点为null的情况,或者当使用双指针,需要从-1位置出发时。但不要滥用,要真能起到简化逻辑才可以。另外就是注意哨兵节点的值要尽可能与常规节点的值区分开来,否则把哨兵节点当成常规节点就会出错。
反转
链表反转是基础的操作,有三种方式:迭代,逆向构造式;借助栈,顺向构建;和递归式,详见206的题解。
题目 | 题解 | 说明 |
---|---|---|
92. 反转链表 II | 题解 | |
206. 反转链表 | 题解 | |
234. 回文链表 | 题解 | |
445. 两数相加 II | 题解 | |
题解 | ||
题解 | ||
题解 |
遍历和随机访问
主要是为了查找某个节点,以进行其他操作。需要别注意的是单链表必须 要找到前一个节点才可以,所以遍历的终止条件一般都是curr.next == target。高级的方法就是双指针和快慢指针,双指针是指两个指针指向不同的位置,然后以同样的速度向前移动;而快慢指针的特点是一个跑的快(两倍步长到next.next),一个跑的慢(常规步长到next),通常从同一个起点出发,注意它们之间是有区别的。
题目 | 题解 | 说明 |
---|---|---|
19. 删除链表的倒数第 N 个结点 | 题解 | 双指针 |
24. 两两交换链表中的节点 | 题解 | |
25. K 个一组翻转链表 | 题解 | |
61. 旋转链表 | 题解 | 与题19类似 |
86. 分隔链表 | 题解 | |
817. 链表组件 | 题解 | |
面试题 02.02. 返回倒数第 k 个节点 | 题解 | |
876. 链表的中间结点 | 题解 | 快慢指针 |
1290. 二进制链表转整数 | 题解 | |
题解 | ||
题解 | ||
题解 |
插入和删除
题目 | 题解 | 说明 |
---|---|---|
24. 两两交换链表中的节点 | 题解 | |
82. 删除排序链表中的重复元素 II | 题解 | |
83. 删除排序链表中的重复元素 | 题解 | |
147. 对链表进行插入排序 | 题解 | |
面试题 02.01. 移除重复节点 | 题解 | |
203. 移除链表元素 | 题解 | |
237. 删除链表中的节点 | 题解 | |
328. 奇偶链表 | 题解 | |
题解 | ||
题解 |
链表合并
题目 | 题解 | 说明 |
---|---|---|
21. 合并两个有序链表 | 题解 | |
23. 合并K个升序链表 | 题解 | |
148. 排序链表 | 题解 | 寻找中间点,归并排序 |
143. 重排链表 | 题解 | |
1669. 合并两个链表 | 题解 | 严格来说不算合并, 主要涉及删除和插入, 以及随机访问 |
题解 |
相交链表
属于高级题目,但套路单一,当作基本套路记住就行了。
题目 | 题解 | 说明 |
---|---|---|
160. 相交链表 | 题解 | |
题解 | ||
题解 |
环形链表
主要分两种,一种是链表部分成环;另外就是整个链表就是环(首尾相接),套路也比较单一,记住就行了。
题目 | 题解 | 说明 |
---|---|---|
剑指 Offer II 029. 排序的循环链表 | 题解 | |
141. 环形链表 | 题解 | |
142. 环形链表 II | 题解 | |
题解 | ||
题解 |
综合
题目 | 题解 | 说明 |
---|---|---|
114. 二叉树展开为链表 | 题解 | |
146. LRU 缓存 | 题解 | |
707. 设计链表 | 题解 | |
题解 | ||
题解 |
双向链表
每个节点有两个指针分别指向下一个节点和前一个节点,这是在实际工作中使用的最多的链表形式,绝大部分操作与单链表是一样的,也是线性的。
双向链表因为有两个指针,所以在删除或者插入的时候需要小心处理好四个指针,其他的东西与单链表是一样的。另外,双链表为了达到最好的效果要使用两个哨兵节点,一个是head,指向头节点,一个是tail是末尾节点。
题目 | 题解 | 说明 |
---|---|---|
1797. 设计一个验证系统 | 题解 | 双向链表,哈希表 LURCache |
题解 |
跳表 SkipList
这是以链表为基础能构造出来的最复杂的数据结构,是二维链表形式,它能够实现log(n)级别的各种操作,效率非常之高,在很多地方替代了平衡二叉树(二叉树只有达到平衡才能到最高的效率,所以工程中使用的二叉树肯定要平衡)。
首先,要明确一下问题,跳表也好,二叉树也好,是解决有序数据集的查询效率的。对于数量为n的数据集来说,如果是无序的肯定是O(n),但如果数据有序,比如一个排好序的数组或者列表就可以用二分查找,或者用BST(二叉搜索树)时间复杂度都会降低到O(logn)。也就是说跳表解决的问题是有序列数据集的查询问题。
基本原理
前面说了,对于有序数据集,如果是用数组或者列表来存储,查询 效率肯定是O(logn)的,但是连续结构有一个问题就是它的插入和删除是O(n)的。链表呢虽然插入和删除可以做到O(1),但是它的随机访问(也即查询)慢要O(n)。那么对于一个有序的单链表来说,有没有办法可以提升它的查询效率呢?(插入和删除以及修改都要以查询为先,只有找到了才方便做插删改)。我们要利用数据已排好序,假如能像BST或者二分那样,能把数据集缩小,就可以提升效率。
假如有一个现成的指针指向有序单链表的中间,那么就可以把中单节点的值与目标值比较,如果目标值大于中间节点,那目标值肯定 在后半段,否则就在前半段。假如有更多的中间节点指针,是不是就是二分查找了?可以用空间换时间,给有序单链表建立索引层,每一层也是一个单链表,它会把下面一层链表分成几段,底层是数据集,即有序单链表。这样,从最上层往下层走,就可以把数据集缩小到一个很小的范围内。极端情况下,可以在1/2,1/4,1/8. … 建立索引层,那这是不是就变成BST了?
这就是跳表的核心想。查询的时候总是从最上层开始,因为每一层也是一个有序链表,当下一个节点值大于目标值时,就需要向下走,然后从这一层的这个节点开始,先向后查询,下一个节点大于目标值时,再向下走,这样当前指针就会一层一层的来回跳着走,故名跳表。
实现细节
跳表的原理并不复杂,容易理解,但从原理到编码仍有很多细节需要考虑,比如如何表示每一层?以及分多少层,分层多能提升效率,但分层多占用的空间也越大,而且如果分的过细,不就变成了二叉树了么。以及说在哪些节点建立索引(也即分层),是按固定的位置(1/2, ¼…)还是按什么规律,因为这直接会影响查询效率。
如何实现分层
分层在节点中实现,常规的节点有一个指针next指向下一个节点,在跳表中节点的next指针是一个数组,数组的长度就是这个节点的层数,以此实现分层,0层是底层,level-1是最上层。这样就能实现每层两个方向的遍历方式,每一层的next指针就是这一层的链表,通过curr.next[i]就能向后遍历。下楼(也即从上层往下一层走)就是level-1就下去了。
当然 这里也可以用指针,比如节点有两个指针一个是next,指向同层的后面的节点,以及down,指针下一层的同位置的指针。但并无概念上的区别,总之层的实现是在每个节点上面的。
从大的维度来说,整体仍是一个从左向右的单链表,分层是在每个节点上面的实现的。
在哪里分层
固定位置分层不可取,因为这就是BST的方式啊,数据集的变化可不会因为位置而改变,比如以1/2, 1/4和1/8这几个位置来分层,那假如数据向1/4后的位置集中了,这就会不平衡,就必须做平衡,会比较麻烦(这也是各种平衡二叉树的痛点)。
跳表用一个比较骚的方式,随机化分层,一个长度为n的有序单链表,每个节点都有机会建立分层索引,这样摊还分析后,整体的效率是最好的。
同时,为了防止分层过于集中,还设立了最大层限制MAX_DEPTH。具体的策略是预先设置一个阈值P(0 < P < 1),每次随机生成一个0~1的浮点数,如果它大于P,那么这个节点的层数加1,否则就返回当前层数(即保持层数不变)。
1 2 3 4 5 6 7 |
|
哨兵节点
为了方便,可以加入哨兵节点head,head犹为重要,这是整个数据结构的入口,并且有了head后插入和删除的逻辑都能得到简化。
标准实现
为了简单,节点值用整数,节点值的有效范围可以设定为0~n-1,长度共是n。
节点
节点,与单链表很像,一个代表值的int,以及一个数组,代表next指针。
需要注意,一个节点的层数在创建节点时就确定了,在节点的生命周期过程中其层数不会变化。因为对跳表数据结构产生变化 的操作只有插入和删除,插入是生成新的节点,插入时层数已确定;删除是把节点移除,自然也没必要再去改变节点本身了。所以节点的数据类型是Immutable的。
1 2 3 4 5 6 7 8 9 |
|
构造
跳表其实就是一个单链表表,所以整体数据结构也不复杂,一个哨兵入口的头节点head,还有当前节点中的最大层数level,和两个阈值P_FACTOR是要不要增加层深的阈值以及最大层数MAX_LEVEL。
1 2 3 4 5 6 7 8 9 10 11 12 |
|
查询
从头节点入口,从其最高层开始查询,具体查询过程与单链表是一样的,持有当前指针,当前指针初化为head节点,不断向后遍历curr直到curr.next[level].val大于目标值,然后走到下一层,继续向后遍历。直到最底层,如果curr.next[0].val等于目标值则找到,否则就是没有,不存在。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
删除
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
插入
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
修改
一般的实现中不会不回修改的接口,因为修改就是删除原节点,然后再插入新节点,所以用删除和插入就可以实现了,没必要再添加一个方法。
运行
为了方便加一个调试方法
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 |
|
运行结果,要用等宽字体看才有效果:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|
相关题目
题目 | 题解 | 说明 |
---|---|---|
1206. 设计跳表 | 题解 | |
题解 | ||
题解 |