前言
- 链表的相关问题，在面试中出现频率较高，这些问题往往也是解决其他复杂问题的基础；
- 在这篇文章里，我将梳理链表问题的问题 & 解法。如果能帮上忙，请务必点赞加关注，这真的对我非常重要。
系列文章
- 《算法面试题 | 链表问题总结》
- 《算法面试题 | 链表相交 & 成环问题》
- 《算法面试题 | 回溯算法解题框架》
- 《数据结构面试题 | 并查集 & 联合 - 查找算法》
- 《数据结构面试题 | 二叉树基础》
延伸文章
删除链表节点 |
提示 & 题解 |
| 203. 移除链表元素 Remove Linked List Elements |
【题解】 |
| 237. 删除链表中的节点 Delete Node in a Linked List |
【题解】 |
| 19. 删除链表的倒数第N个节点 Remove Nth Node From End of List |
【题解】 |
| 86. 分隔链表 Partition List |
【题解】 |
| 328. 奇偶链表 Odd Even Linked List |
【题解】 |
| 83. 删除排序链表中的重复元素 Remove Duplicates from Sorted List |
|
| 82. 删除排序链表中的重复元素 II Remove Duplicates from Sorted List II |
|
| 725. 分隔链表 Split Linked List in Parts |
|
| （扩展）0876. 链表的中间结点 Middle of the Linked List |
【题解】 |
反转链表 |
提示 & 题解 |
| 206. 反转链表 Reverse Linked List |
【题解】 |
| 92. 反转链表 II Reverse Linked List II |
【题解】 |
| 234. 回文链表 Palindrome Linked List |
【题解】 |
| 25. K 个一组翻转链表 Reverse Nodes in k-Group |
合并有序链表 |
提示 & 题解 |
| 21. 合并两个有序链表 Merge Two Sorted Lists |
【题解】 |
| 23. 合并K个升序链表 Merge k Sorted Lists |
【题解】 |
排序链表 |
提示 & 题解 |
| 147. 对链表进行插入排序 Insertion Sort List |
【题解】 |
| 148. 排序链表 Sort List |
【题解】 |
其他 |
提示 & 题解 |
| 24. 两两交换链表中的节点 Swap Nodes in Pairs |
|
| 143. 重排链表 Reorder List |
|
| 138. 复制带随机指针的链表 Copy List with Random Pointer |
|
| 380. 常数时间插入、删除和获取随机元素 Insert Delete GetRandom O(1) |
|
| 381. O(1) 时间插入、删除和获取随机元素 - 允许重复 Insert Delete GetRandom O(1) - Duplicates allowed |
|
| 707. 设计链表 Design Linked List |
|
| 430. 扁平化多级双向链表 Flatten a Multilevel Doubly Linked List |
|
| 817. 链表组件 Linked List Components |
【题解】 |
目录
1. 概述
1.1 链表的定义
链表是一种常见的基础数据结构，是一种线性表。与顺序表不同的是，链表中的每个节点不是顺序存储的，而是通过节点的指针域指向到下一个节点。
1.2 链表的优缺点
| 对比 | 优点 | 缺点 |
| 内存管理 | 充分利用计算机内存空间，更灵活地分配内存空间 | 指针域增加了内存消耗 |
| 操作效率 | 能在 O(1)O(1)O(1) 时间内删除或添加节点（前提是前驱节点已知） | 失去了数组随机访问的特性，查询对应位置的节点需要 O(n)O(n)O(n) 时间 |
| 数据容量 | 需要预先分配内存空间，容量不足需要扩容 | 不需要预先分配内存空间，不需要扩容 |
| 访问性能 | / | CPU 缓存行无法提高效率 |
1.3 链表的类型
单链表、双链表、循环链表、静态链表
2. 删除链表节点
删除链表节点时，考虑到可能删除的是链表的第一个节点（没有前驱节点），为了编码方便，可以考虑增加一个 哨兵节点。其中，在删除链表的倒数第 N 个节点问题里，使用快慢指针在一趟扫描里找出倒数第 N 个节点是比较重要的编程技巧。
237. Delete Node in a Linked List 删除链表中的节点【题解】
203. Remove Linked List Elements 移除链表元素【题解】
不移除野指针 class Solution { fun removeElements(head: ListNode?, `val`: Int): ListNode? { // 哨兵节点 val sentinel = ListNode(-1) sentinel.next = head var pre = sentinel var cur: ListNode? = sentinel while (null != cur) { if (`val` == cur.`val`) { // 移除 pre.next = cur.next } else { pre = cur } cur = cur.next } return sentinel.next } } 移除野指针 class Solution { fun removeElements(head: ListNode?, `val`: Int): ListNode? { // 哨兵节点 val sentinel = ListNode(-1) sentinel.next = head var pre = sentinel var cur: ListNode? = sentinel while (null != cur) { val removeNode = if (`val` == cur.`val`) { // 移除 pre.next = cur.next cur } else { pre = cur null } cur = cur.next if (null != removeNode) { removeNode.next = null } } return sentinel.next } } 复制代码
19. Remove Nth Node From End of List 删除链表的倒数第N个节点【题解】
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
class Solution { fun removeNthFromEnd(head: ListNode, n: Int): ListNode? { // 哨兵节点 val sentinel = ListNode(-1) sentinel.next = head var fast: ListNode? = sentinel var slow: ListNode? = sentinel for (index in 0 until n) { fast = fast!!.next } // 找到倒数第 k 个节点的前驱 while (null != fast!!.next) { fast = fast.next slow = slow!!.next } slow!!.next = slow.next!!.next return sentinel.next } } 复制代码
复杂度分析：
- 时间复杂度：每个节点扫描一次，时间复杂度为 O(n)
- 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)
类似地，876. Middle of the Linked List 链表的中间结点【题解】 也是通过快慢指针来找到中间节点的：
class Solution { fun middleNode(head: ListNode?): ListNode? { if (null == head || null == head.next) { return head } var fast = head var slow = head while (null != fast && null != fast.next) { fast = fast.next!!.next slow = slow!!.next } return slow } } 复制代码
86. Partition List 分隔链表【题解】
删除链表中等于给定值 val 的所有节点。
思路：分隔链表无非是先将大于等于 val 的节点从原链表中移除到第二个链表中，最后再拼接两个链表。
class Solution { fun partition(head: ListNode?, x: Int): ListNode? { if (null == head) { return null } // 哨兵节点 val sentinel = ListNode(-1) sentinel.next = head var pre = sentinel // 第二链表 var bigHead : ListNode? = null var bigRear = bigHead var cur = head while (null != cur) { if (cur.`val` >= x) { // 大于等于：移除 pre.next = cur.next if(null == bigHead){ bigHead = cur bigRear = cur }else{ bigRear!!.next = cur bigRear = cur } } else { pre = cur } if (null == cur.next) { // 拼接 pre.next = bigHead bigRear?.next = null break } cur = cur.next } return sentinel.next } } 复制代码
复杂度分析：
- 时间复杂度：每个节点扫描一次，时间复杂度为 O(n)
- 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)
328. Odd Even Linked List 奇偶链表【题解】
思路：奇偶链表无非是先将奇节点放在一个链表里，偶节点放在另一个链表里，最后把偶节点接在奇链表的尾部
class Solution { fun oddEvenList(head: ListNode?): ListNode? { if (null == head) { return null } var odd: ListNode = head var even = head.next val evenHead = even while (null != even && null != even.next) { // 偶节点 odd.next = even.next odd = odd.next!! // 奇节点 even.next = odd.next even = even.next } odd.next = evenHead // 头节点不动 return head } } 复制代码
83. Remove Duplicates from Sorted List 删除排序链表中的重复元素
82. Remove Duplicates from Sorted List II 删除排序链表中的重复元素 II
3. 反转链表
反转链表问题在面试中出现频率 非常非常高，相信有过几次面试经验的同学都会同意这个观点。在这里，我找出了 4 道反转链表的问题，从简单延伸到困难，快来试试吧。
206. 反转链表 Reverse Linked List【题解】
反转一个单链表。
解法1：递归
class Solution { fun reverseList(head: ListNode?): ListNode? { if(null == head || null == head.next){ return head } val prefix = reverseList(head.next) head.next.next = head head.next = null return prefix } } 复制代码
复杂度分析：
- 时间复杂度：每个节点扫描一次，时间复杂度为 O(n)
- 空间复杂度：使用了递归栈，空间复杂度为 O(n)
解法2：迭代
class Solution { fun reverseList(head: ListNode?): ListNode? { var cur: ListNode? = head var headP: ListNode? = null while (null != cur) { val tmp = cur.next cur.next = headP headP = cur cur = tmp } return headP } } 复制代码
复杂度分析：
- 时间复杂度：每个节点扫描一次，时间复杂度为 O(n)
- 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)
92. 反转链表 II Reverse Linked List II【题解】
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
class Solution { fun reverseBetween(head: ListNode?, m: Int, n: Int): ListNode? { if (null == head || null == head.next) { return head } // 哨兵节点 val sentinel = ListNode(-1) sentinel.next = head var rear = sentinel // 1. 找到反转开始位置前驱节点 var cur = sentinel for (index in 0 until m - 1) { cur = cur.next!! rear = cur } // 2. 反转指定区域 rear.next = reverseList(rear.next!!, n - m + 1) return sentinel.next } /** * 反转指定区域 * @param size 长度 */ fun reverseList(head: ListNode, size: Int): ListNode? { var cur: ListNode? = head var headP: ListNode? = null // 反转的起始点需要连接到第 n 个节点 val headTemp = head var count = 0 while (null != cur && count < size) { val tmp = cur.next cur.next = headP headP = cur cur = tmp count++ } // 连接到第 n 个节点 headTemp.next = cur return headP } } 复制代码
复杂度分析：
- 时间复杂度：每个节点扫描一次，时间复杂度为 O(n)
- 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)
234. Palindrome Linked List 回文链表【题解】
请判断一个链表是否为回文链表。
思路：使用快慢指针找到中间节点，反转后半段链表（基于反转链表 II），比较前后两段链表是否相同，最后再反转回复到原链表。
class Solution { fun isPalindrome(head: ListNode?): Boolean { if (null == head || null == head.next) { return true } // 1. 找到右边中节点（右中节点） var fast = head var slow = head while (null != fast && null != fast.next) { slow = slow!!.next fast = fast.next!!.next } // 2. 反转后半段 val reverseP = reverseList(slow!!) // 3. 比较前后两段是否相同 var p = head var q: ListNode? = reverseP var isPalindrome = true while (null != p && null != q) { if (p.`val` == q.`val`) { p = p.next q = q.next } else { isPalindrome = false break } } // 4. 恢复链表 reverseList(reverseP) return isPalindrome } /** * 反转链表 */ private fun reverseList(head: ListNode): ListNode { // 略，见上一节... } } 复制代码
复杂度分析：
- 时间复杂度：每个节点扫描两次，时间复杂度为 O(n)
- 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)
25. K 个一组翻转链表 Reverse Nodes in k-Group
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
4. 合并有序链表
合并有序链表问题在面试中出现频率 较高，其中，合并两个有序链表 是比较简单的，而它的进阶版 合并K个升序链表 要考虑的因素更全面，难度也有所增强，快来试试吧。
21. Merge Two Sorted Lists 合并两个有序链表【题解】
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
class Solution { fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? { if (null == l1) return l2 if (null == l2) return l1 // 哨兵节点 val sentinel = ListNode(-1) var rear = sentinel var p = l1 var q = l2 while (null != p && null != q) { if (p.`val` < q.`val`) { rear.next = p rear = p p = p.next } else { rear.next = q rear = q q = q.next } } rear.next = if (null != p) p else q return sentinel.next } } 复制代码
复杂度分析：
- 时间复杂度：每个节点扫描一次，时间复杂度为 O(m+n)
- 空间复杂度：使用了常量级别变量，空间复杂度为 O(1)
23. Merge k Sorted Lists 合并K个升序链表【题解】
给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。
解法1：暴力法
思路1：与合并两个有序链表类似，每轮从 k 个链表中取出最小的节点，并插入结果链表中。其中，从 k 个数中取出最小节点的时间复杂度为 O(k)
思路2：这个思路与上个思路类似，时间复杂度和空间复杂度页相同，即：依次将 k 个链表与结果链表合并。
略 复制代码
复杂度分析：
- 时间复杂度：O(nk∗k)
- 空间复杂度：O(1)
解法2：排序法
思路：用一个数组保存所有节点之后，进行快速排序，随后将数组输出单链表。
class Solution { fun mergeKLists(lists: Array<ListNode?>): ListNode? { if (lists.isNullOrEmpty()) { return null } // 1. 用一个数组保存所有节点 val array = ArrayList<ListNode>() for (list in lists) { var cur = list while (null != cur) { array.add(cur) cur = cur.next } } // 2. 快速排序 array.sortWith(Comparator { node1, node2 -> node1.`val` - node2.`val` }) // 3. 输出为链表 val newHead = ListNode(-1) var rear = newHead for (node in array) { rear.next = node rear = node } return newHead.next } } 复制代码
复杂度分析：
- 时间复杂度：合并节点时间 O(nk)，快速排序时间 O(nk∗lgnk输出单链表时间 O(nk)，总体时间复杂度 O(nk∗lgnk)
- 空间复杂度：使用数组空间 O(nk)
解法3：归并法
思路：将 k 组链表分为两部分，然后递归地处理两组链表，最后再合并起来。
class Solution { // 合并 k 个有序链表 fun mergeKLists(lists: Array<ListNode?>): ListNode? { if (lists.isNullOrEmpty()) { return null } return mergeKLists(lists, 0, lists.size - 1) } fun mergeKLists(lists: Array<ListNode?>, left: Int, right: Int): ListNode? { if (left == right) { return lists[left] } // 归并 val mid = (left + right) ushr 1 return mergeTwoLists( mergeKLists(lists, left, mid), mergeKLists(lists, mid + 1, right) ) } // 合并两个有序链表 fun mergeTwoLists(l1: ListNode?, l2: ListNode?): ListNode? { // 略，见上一节... } } 复制代码
复杂度分析：
- 时间复杂度：时间主要在合并链表的操作上，从递归树可以看出，递归树每一层的节点个数都是 nknknk，而递归树的高度 h=lgk，因此总的时间复杂度为 O(nk∗lgk)
- 空间复杂度：使用了递归栈，空间复杂度为 O(lgk)
解法4：小顶堆法
思路：在解法1中，从 k 个数中取出最小节点的时间复杂度为 O(k)O(k)O(k)，可以使用最小堆（优先队列）来优化到 O(lgk)。其中，堆内节点始终是 k 个链表的未处理部分的表头。
class Solution { // 合并 k 个有序链表 fun mergeKLists(lists: Array<ListNode?>): ListNode? { if (lists.isNullOrEmpty()) { return null } // 最小堆 val queue = PriorityQueue<ListNode>(lists.size) { node1, node2 -> node1.`val` - node2.`val` } // 1. 建堆 for (list in lists) { if (null != list) { queue.offer(list) } } val sentinel = ListNode(-1) var rear = sentinel // 2. 出队 while (queue.isNotEmpty()) { val node = queue.poll()!! // 输出到结果链表 rear.next = node rear = node // 存在后继节点，加入堆中 if (null != node.next) { queue.offer(node.next) } } return sentinel.next } } 复制代码
复杂度分析：
- 时间复杂度：大小为 k 的二叉堆建堆时间为 O(k)取堆顶的时间为 O(1)，插入一个新节点的时间为 O(lgk)，总体时间复杂度为 O(nk∗lgk)
- 空间复杂度：二叉堆空间为 O(k)
5. 排序链表
147. Insertion Sort List 对链表进行插入排序 |【题解】
148. Sort List 排序链表【题解】
6. 环形链表
链表相交 & 成环问题可以归为一类问题，在面试中出现频率较高；在之前的一篇文章里，我们单独讨论过：《算法面试题 | 链表相交 & 成环问题》
