力扣刷题笔记 #08 链表

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

题目描述：

方法1：

方法2：

方法3：

坑点：

扫描链表

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

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

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 后面所有结点已经反转，只需再反转 head 和 head->next 中间的指针，并将 head 指向空」。复杂度 \(O(n)\)，只用到了单指针。

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

题目描述：给定单链表的头节点 head（有值），每 K 个节点一组原地反转，不足 K 个不反转。

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

方法2：递归，边界条件是不足 K 个时，无需反转。通过循环找到第 \(K\) 个节点 tail，子问题是「tail 后面所有结点已经反转，只需再反转 head 到 tail->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)

题目描述：给你两个单链表的头节点 headA 和 headB，请你找出并返回两个单链表相交的起始节点。

方法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。

使用双向链表的原因：get 或 put 需要将已有关键字移到首部，从链表中间删除一个节点需要知道其前序节点的指针，双向链表可以 \(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)\)。