力扣刷题笔记 #08 链表

本文最后更新于:2024年7月8日 晚上

本文包含「链表」类型题中的:扫描链表、链表模拟等。持续更新中。

题目描述

方法1

方法2

方法3

坑点

扫描链表

链表的特点是只能正向遍历,通常由指针来扫描,个别题目可以用递归法解决(逆向思维)。

小技巧:链表问题通常没有空间复杂度的限制,因为其本身的存储也需要 \(O(n)\),因此面试题通常要求「原地操作」。如果只追求解题,完全可以将链表 \(O(n)\) 转为数组后再操作,最后再 \(O(n)\) 转回链表。

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
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};

vector<int> to_vector(ListNode *head){
vector<int> ret;
for (auto it = head; it; it = it->next)
ret.push_back(it->val);
return ret;
}

ListNode *to_list(const vector<int> &v){
if (v.empty()) return NULL;
ListNode *ret = new ListNode(v[0]);
ListNode *it = ret;
for (int i = 1; i < v.size(); ++ i){
it->next = new ListNode(v[i]);
it = it->next;
}
return ret;
}

2. 两数相加 (E)

题目描述:两个非空链表,每个结点代表十进制的一位(表头代表最低位),将其相加,并以相同形式返回一个新链表。

方法:直接遍历两个链表,存储进位,复杂度 \(O(n)\)

坑点:并不是两个链表都遍历完就结束,还要考虑最后的进位

234. 回文链表 (E)

题目描述:给定一个链表,判断链表节点的值是否构成回文序列。

方法1:暴力,将链表转为数组,再用对撞双指针遍历,时空复杂度均为 \(O(n)\)

方法2:栈,第一次遍历链表将元素压入栈中,第二次遍历时逐个弹出匹配,可以实现逆向遍历。同理,也可以用递归反向迭代,同时用递归函数外的变量正向迭代,原理相同。时空复杂度均为 \(O(n)\)

方法3:修改原链表,使用快慢指针获得链表中点后,将后半部分反转,再用双指针进行配对。空间复杂度 \(O(1)\)

方法4:字符串哈希,将链表当成数字字符串,计算正向哈希值和反向哈希值,如果两个值相等则可以认为构成回文。无需修改原链表,时间复杂度 \(O(n)\),空间复杂度 \(O(1)\)

正向值和反向值可以一次遍历算出,二者的方法不一样。需要定义 \(base\)\(mod\),以及递增的乘子 \(mul\)

  • 正向哈希值:\(pos=(pos*base+val)\% mod\)
  • 反向哈希值:\(neg=(neg+mul*val)\%mod\)\(mul=mul*base \% mod\)

21. 合并两个有序链表 (E)

题目描述:将两个升序链表合并为一个新的升序链表并返回。

方法1:正向扫描,当两个链表都不为空时取较小者;当一个为空时,将链表末尾指向另一个即可。在实现时可以用一个虚拟 head 作为头,复杂度 \(O(n+m)\)

方法2:递归,边界条件是一个为空时,返回另一个。都不为空时,取出较小者,指向「剩下的两条链表递归合并的结果」,并返回较小者所在的链表头。

23. 合并 k 个升序链表 (H)

题目描述:一个链表数组,里面有 \(k\) 个长为 \(n\) 的链表,每个链表都按升序排列,将所有链表合并成一个升序链表。

方法1:顺序合并,每次合并的复杂度是两个链表长度之和,第一次是 \(2n\),第二次是 \(3n\),以此类推到 \(k-1\) 次,累加得到总复杂度为 \(O(k^2 n)\),空间复杂度 \(O(1)\)

方法2优先队列,维护每个链表未被合并的首个元素,每次取出最小者,再将其下一个元素放入队列。时间复杂度 \(O(kn\log k)\),维护队列需要 \(O(k)\) 的空间。

方法3:分治归并,将长度相等的链表两两归并,第一轮 \(k\) 个链表合并为 \(k/2\) 个,总长度 \(kn\);第二轮合并为 \(k/4\) 个,总长度还是 \(kn\),以此类推到 \(\log k\) 次,时间复杂度 \(O(kn\log k)\),递归需要 \(O(\log k)\) 的栈空间。

206. 反转链表 (E)

题目描述:给定单链表的头节点 head(有值),返回原地反转后的链表(不能使用新链表、临时栈)。

方法1:迭代(三指针),prev 指向 〇,curr 指向 ①,temp 指向 ②。每次将 ①->② 反转。复杂度 \(O(n)\)

方法2:头插法,虚拟一个哑结点(Dummy Node)指向第一个结点,每次将下一个点插到哑结点之后,复杂度 \(O(n)\)

方法3:递归,边界条件是单结点时,无需反转。子问题是「head 后面所有结点已经反转,只需再反转 headhead->next 中间的指针,并将 head 指向空」。复杂度 \(O(n)\),只用到了单指针。

25. K 个一组翻转链表 (H)

题目描述:给定单链表的头节点 head(有值),每 K 个节点一组原地反转,不足 K 个不反转

方法1:两次遍历,第一次遍历计数链表长度 \(Len\),第二次遍历翻转 \(Len/K\) 次子链表,时间复杂度 \(O(n)\)

方法2:递归,边界条件是不足 K 个时,无需反转。通过循环找到第 \(K\) 个节点 tail,子问题是「tail 后面所有结点已经反转,只需再反转 headtail->next 的指针,并将 head 指向 tail」。复杂度 \(O(n)\)

坑点:注意子问题处理完head 会变成第 \(K\) 个节点,不能直接返回

双指针定位

19. 删除链表的倒数第 N 个结点 (M)

题目描述:一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。

方法1:强行计算链表长度,至少需要遍历两次。

方法2:借助栈,将所有结点依次入栈再弹出,第 n 个弹出的结点就是要删除的结点,此时栈顶结点就是其前驱结点。

方法3快慢指针,快指针先走 n 步,随后快慢指针同步前进。遍历一次且空间复杂度 \(O(1)\)

坑点:链表的倒数第 n 个结点可能就是头结点,此时快指针已经指向 nullptr,慢指针是不需要继续前进的,直接返回 head->next 即可。

拓展:如果要删除链表正中间结点,只需用步长为 2 的快指针和步长为 1 的慢指针遍历即可。

141. 环形链表 (E)

题目描述:给一个链表的头节点 head ,判断链表中是否有环。

方法1:哈希集合,将便利到的结点的指针存储到集合中,每次先 count 判断。时空复杂度均 \(O(n)\)

方法2快慢指针,用步长为 2 的快指针和步长为 1 的慢指针遍历,如果两指针相遇,则一定有环。空间复杂度 \(O(1)\)

坑点:快慢指针的初值不应该都设置为 head,否则可能会直接退出循环,可以将快指针设为 head->next,或者直接先让两个指针各前进一步再判断。

扩展:如何统计环的长度?快慢指针相遇后继续移动,直到第二次相遇。两次相遇间的移动次数即为环的长度。

142. 环形链表 II (M)

题目描述:给一个链表的头节点 head ,返回链表环的入口(开始入环的第一个节点)。

方法1:哈希集合,同上题,当 count()!=0 时即找到入口,返回即可。时空复杂度均 \(O(n)\)

方法2:快慢指针,用步长为 2 的 \(fast\) 和步长为 1 的 \(slow\) 遍历,两指针相遇后,用一个步长为 1 的 \(pos\)head 出发,且 \(slow\) 继续以步长 1 前进。当 \(slow\)\(pos\) 第一次相遇时,相遇处即为环的入口。空间复杂度 \(O(1)\)

快慢指针第一次相遇时,设慢指针路程 \(s\),快指针路程 \(f=2s\),环的长度为 \(r\)。显然 \(f=s+nr\)\(n\) 为套圈数。联立两式可知 \(s=nr\)

head 到环的入口需要走的路程为 \(p\),显然 \(p+nr\) 也是环的入口,所以 \(p+s\) 也是环的入口。令一个定位指针从 head 出发走 \(p\),同时慢指针继续走 \(p\),二者就会在环的入口相遇。

287. 寻找重复数 (M)

题目描述:给定一个包含 \(n + 1\) 个整数的数组,其数字都在 \([1, n]\) 范围内,假设数组中有且仅有一个重复的整数,找出数组中重复的数字,要求空间复杂度 \(O(1)\)

方法1:二分答案,定义 \(cnt[i]\) 表示数组中小于等于 \(i\) 的数的个数,假设重复数是 \(x\),则 \([1,x-1]\) 里所有数都满足 \(cnt[i] \leq i\);而 \([x,n]\) 里的所有数满足 \(cnt[i]>i\)。因此可以二分枚举 \(x\) 直到找到。时间复杂度 \(O(n\log n)\)

方法2:二进制,预处理 \([1,n]\)\(n\) 个数「每一位\(1\)个数之和」,如果当前数组的「每一位\(1\)个数之和」大于期望值,则说明重复数的这一位\(1\)。遍历每一位即可,时间复杂度 \(O(n \log n)\)

方法3:抽象成环形链表寻找入口,快慢指针,先用 \(fast\)\(slow\) 相遇,再用 \(pos\)\(slow\) 相遇,时间复杂度 \(O(n)\)

将数组和下标抽象为链表,数组的值代表链表下一个节点的下标。由于不存在数字 0,可下标为 0 的元素作为链表头节点。由于数组中存在重复数字,对应链表中有多个指针指向同一个顶点,则链表中必有环。找出重复数等价于找出链表环的入口

160. 相交链表 (E)

题目描述:给你两个单链表的头节点 headAheadB,请你找出并返回两个单链表相交的起始节点

方法1:哈希集合,遍历 headA 并将每个节点加入集合,然后遍历 headB,对每个结点检查是否在集合中。时间复杂度为 \(O(m+n)\),空间复杂度为 \(O(m)\)

方法2:暴力,消除两个链表的长度差,遍历两个链表并计数得到长度,长的先走几步,然后一起走并判断两指针是否相等。时间复杂度为 \(O(m+n)\),空间复杂度 \(O(1)\)

方法3:双指针,消除两个链表的长度差,将两个链表拼接到一起就是等长。具体实现:当指针遍历完一个链表时,再次指向另一个链表的头节点继续遍历。时间复杂度 \(O(m+n)\),空间复杂度 \(O(1)\)

链表模拟

Todo 707. 设计链表

146. LRU 缓存 (M)

题目描述:设计一个 LRUCache 类,实现以下功能:

  • LRUCache(int capacity):以正整数作为容量 capacity 初始化 LRU 缓存;
  • int get(int key):如果 key 存在于缓存中,则返回其值,否则返回 -1,要求 \(O(1)\)
  • void put(int key, int value):如果 key 存在,则变更其值为 value;如果不存在,则向缓存中插入键值对。如果插入操作导致数量溢出 ,则应该逐出最久未使用(LRU)的关键字,要求 \(O(1)\)

方法:双向链表 + 哈希表。链表用来存放关键字序列,首部表示 MRU,尾部表示 LRU,put 关键字默认放在首部,get 关键字默认移到首部,溢出时首先移除尾部。时间复杂度 \(O(1)\)

使用两个哈希表存储关键字到链表节点关键字到值的映射:前者用来 \(O(1)\) 找到关键字在链表中的位置,方便移动;后者用来存值,也可以省略并在链表中存 pair。

使用双向链表的原因:getput 需要将已有关键字移到首部,从链表中间删除一个节点需要知道其前序节点的指针,双向链表可以 \(O(1)\) 获取。

注意:移除尾部时并非利用了双向链表的特性,维护一个 \(tail\) 指针同样可以 \(O(1)\) 移除尾部。

460. LFU 缓存 (H)

题目描述:设计一个 LFUCache 类,实现以下功能:

  • LFUCache(int capacity)int get(int key) 同上;
  • void put(int key, int value):如果插入操作导致数量溢出 ,则应该逐出最不经常使用(LFU)的关键字。当存在平局(即两个或更多个键具有相同使用频率)时,应该去除最近最久未使用的键。

方法1:哈希表 + 集合。用集合存储 \(Node\) 结构体,\(Node\) 中包含键值对和使用频率、最近使用时间,并且自定义结构体比较函数。每次更新需要把元素从 set 取出、修改、再重新插入,时间复杂度 \(O(\log n)\)

方法2:十字链表 + 双哈希表。一个哈希表用频率为索引, 每个索引存放一个双向链表;另一个哈希表以关键字为索引,存放链表节点的指针。维护一个 \(minFreq\),每次删除操作直接从对应的链表中删,时间复杂度 \(O(1)\)


力扣刷题笔记 #08 链表
https://hwcoder.top/LeetCode-LinkList
作者
Wei He
发布于
2022年10月2日
许可协议