【高频面试题】快慢指针及相关应用

1 简介

快慢指针的解法在面试题中非常常见，尤其是涉及到链表有环的情况下。
我们常说的快慢指针解法（Floyd's Cycle-Finding Algorithm）会在链表的头部初始化两个指针，分别称为快指针和慢指针。通过它们移动速度的差异以及最终相遇的位置（或无法相遇的事实），可以高效地解决一系列问题。本文主要介绍快慢指针要应对的各种题型及相关应用。

2 相关应用

• 判断链表是否有判环
• 寻找链表的中点
• 寻找链表的倒数第k个节点
• 寻找链表的交点
• 寻找链表的入环点
• 计算链表的环的长度

3 相关题目

• LeetCode141. 环形链表

• LeetCode142. 环形链表II

• LeetCode876. 链表的中间结点

• 面试题 02.02. 返回倒数第 k 个节点

• LeetCode143. 重排链表

• LeetCode287. 寻找重复数

• LeetCode234. 回文链表

4 典型例题

4.1 判断链表是否有环

• 题目描述：给定一个单向链表的头指针，判断链表中是否有环
• 解题思路：这是快慢指针最著名、最基础的应用。这里用到两组指针：快指针和满指针，快指针每次移动两步，慢指针每次移动一步。这类似于龟兔赛跑，兔子跑到最后会套乌龟一圈最终相遇，因此，如果有环两个指针一定会相遇。
• 时空复杂度：时间复杂度$O(n)$, 空间复杂度$O(1)$
• 代码实现如下：

class Solution {
public:// LeetCode141bool hasCycle(ListNode* head) {ListNode* slow = head, *fast = head; while (fast && fast->next) {slow = slow->next; fast = fast->next->next; if (fast == slow)return true;}return false; }
};

4.2 寻找链表的入环点

• 题目描述：给定一个单向链表的头指针，返回链表开始入环的第一个节点，如果链表无环，则返回 null。(不能修改链表)
• 解题思路：本题的做法比较巧妙。用两个指针 slow, fast分别从起点开始走，slow每次走一步，fast每次走两步。如果过程中 fast 走到null，则说明不存在环。否则当 fast和 slow相遇后，让 slow返回起点， fast 待在原地不动，然后两个指针每次分别走一步，当相遇时，相遇点就是环的入口。
• 推导：假设入环前的路程为$a$,环长为$b$。设慢指针走了$x$步时,快慢指针相遇，此时快指针走了$2x$步。显然$2\ast x-x=n\ast b$(快指针比慢指针多走$n$圈),即$x=n\ast b$，也就是慢指针走过的路程为$n\ast b$,则慢指针在环中走了$n\ast b-a$步，他还要再往前走$a$步才是完整的$n$圈。所以，我们让头节点和慢指针同时往前走，当他们相遇时，刚好走过这$a$步。
• 时空复杂度：时间复杂度$O(n)$, 空间复杂度$O(1)$
• 代码实现如下：

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *p = head, *q = head;while (q && q->next) {p = p->next;q = q->next->next;if (p == q) {ListNode *tmp = head;while (tmp != p) {tmp = tmp->next;p = p->next;}return tmp;}}return nullptr;}
};

4.3 寻找链表的中点

• 题目描述：给定一个单向链表的头指针，找到链表的中点
• 解题思路：快慢指针，快指针每次走两步，慢指针每次走一步，使快指针走的距离始终是慢指针的两倍, 当快指针走到链表尾部时，慢指针正好走到链表中间。
• 时空复杂度：时间复杂度$O(n)$, 空间复杂度$O(1)$
• 代码实现如下：

class Solution {
public:// LeetCode876ListNode* middleNode(ListNode* head) {ListNode *slow = head, *fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;}
};

4.4 寻找链表的倒数第k个节点

• 题目描述：给定一个单向链表的头指针，找到链表的中点
• 解题思路：快慢指针，先让一个指针走k步，然后两个一起走,使得fast与slow始终保持k步距离，当fast到尾节点时，slow便指向倒数第k个节点。
• 时空复杂度：时间复杂度$O(n)$, 空间复杂度$O(1)$
• 代码实现如下：

class Solution {
public:int kthToLast(ListNode* head, int k) {ListNode *slow = head, *fast = head;while (k --) {fast = fast->next;}while (fast) {slow = slow->next;fast = fast->next;}return slow->val;}
};

4.5 重排链表 （反转链表+找链表中点+合并链表）

• 题目描述：给定一个链表 $L:L0\to L1\to \dots \to Ln-1\to Ln$，将它变成 $L0\to Ln\to L1\to Ln-1\to L2\to Ln-2\to \dots$
• 解题思路：先将找到后半部分链表，再将其反转，最后从head开始依次插入更新节点。
• 时空复杂度：时间复杂度$O(n)$, 空间复杂度$O(1)$
• 代码实现如下：

class Solution {
public:// 反转链表ListNode* reverseList(ListNode* head) {ListNode *prev = nullptr;ListNode *cur = head;while (cur) {ListNode *next = cur->next;cur->next = prev;prev = cur, cur = next;}return prev;}// 链表的中间节点ListNode* middleNode(ListNode* head) {ListNode *slow = head, *fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;}void reorderList(ListNode* head) {ListNode *mid = middleNode(head); // 找出后半部分ListNode *head2 = reverseList(mid); // 反转后半部分while (head2->next) { // 注意这个条件 mid后面长度奇偶都可以// 保存下一个节点ListNode *nxt = head->next;ListNode *nxt2 = head2->next;// 连接head->next = head2;head2->next = nxt;// 移至nexthead = nxt;head2 = nxt2;}}
};

也可参考官方解法，将后半的链表断开再合并

class Solution {
public:// 反转链表ListNode* reverseList(ListNode* head) {ListNode *prev = nullptr;ListNode *cur = head;while (cur) {ListNode *next = cur->next;cur->next = prev;prev = cur, cur = next;}return prev;}// 链表的中间节点（返回中间节点的前一个节点）ListNode* middleNode(ListNode* head) {ListNode* slow = head;ListNode* fast = head;while (fast->next && fast->next->next) {slow = slow->next;fast = fast->next->next;}return slow;}void mergeList(ListNode *head1, ListNode *head2) {while (head1 && head2) {ListNode *p = head1->next, *q = head2->next;head1->next = head2;head1 = p;head2->next = head1;head2 = q;}}void reorderList(ListNode* head) {if (head == nullptr) return;ListNode* mid = middleNode(head); // 中间节点ListNode* l1 = head; ListNode* l2 = mid->next;		  mid->next = nullptr;l2 = reverseList(l2);			  // 中间节点之后的全部反转mergeList(l1, l2);				  // 合并}
};

4.6 寻找重复数（快慢指针 or 二分）

• 题目描述：给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数。假设nums只有 一个重复的整数 ，返回这个重复的数 。你设计的解决方案必须 不修改 数组 nums 且只用常量级 $O(1)$ 的额外空间。
• 解题思路：
  • 快慢指针：我们对nums数组建图，每个位置 i 连一条 i→nums[i] 的边。由于存在的重复的数字 target，因此 target 这个位置一定有起码两条指向它的边，因此整张图一定存在环，且我们要找到的target 就是这个环的入口，那么整个问题就等价于求链表环的入口。以[1, 3, 4, 2, 2]为例，构建0->1, 1->3, 2->4, 3->2, 4->2构成1->3->2->4->2这就形成了一个2->4->2->...的环。时间复杂度$O(n)$, 空间复杂度$O(1)$
  • 二分查找：因为在区间[1, n]存在重复的数，且只有一个数字是出现多次的，其余数字要么出现，要么不出现。设cnt表示某一数字num在数组中出现的次数，那么当cnt>num且num是从前往后第一个满足这个条件的数字时，该数字是要寻找的重复数，所以采用二分查找找第一个cnt大于本身数值的数。时间复杂度$O(logn)$, 空间复杂度$O(1)$
• 代码实现如下：

class Solution {
public:int binarySearch(vector<int> &nums) {int n = nums.size();// 二分 第一个cnt大于本身数值的数int left = ranges::min(nums) - 1, right = ranges::max(nums) + 1;while (left + 1 < right) {int mid = left + (right - left) / 2;int cnt = 0;for (auto &x : nums) cnt += x <= mid;if (cnt > mid) right = mid;else left = mid;}return right;}int findDuplicate(vector<int>& nums) {int fast = 0, slow = 0;do {slow = nums[slow];fast = nums[nums[fast]];} while (fast != slow);slow = 0;while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;}
};

4.7 回文链表

• 题目描述：给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false。
• 解题思路：
  • 快慢指针：找中间节点+反转链表，时间复杂度$O(n)$, 空间复杂度$O(1)$
  • 栈：时间复杂度$O(n)$, 空间复杂度$O(n)$
• 代码实现如下：

/*** Definition for singly-linked list.* 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) {}* };*/
class Solution {
public:// 找链表中间节点ListNode *middleNode(ListNode *head) {ListNode *slow = head, *fast = head;while (fast && fast->next) {slow = slow->next;fast = fast->next->next;}return slow;}// 反转链表ListNode *reverseList(ListNode *head) {ListNode *pre = nullptr, *cur = head;while (cur) {ListNode * nxt = cur->next;cur->next = pre;pre = cur;cur = nxt;}return pre;}// 栈bool check(ListNode *head) {stack<int> st;ListNode *p = head;while (p) {st.push(p->val);p = p->next;}while (head) {if (head->val != st.top()) {return false;}head = head->next;st.pop();}return true;}bool isPalindrome(ListNode* head) {ListNode *mid = middleNode(head);ListNode *p = reverseList(mid);while (p) {if (p->val != head->val) return false;p = p->next;head = head->next;}return true;//return check(head);}
};

5 参考

• 一文看懂快慢指针解法
• 环形链表II【基础算法精讲 07】
• 【图解】一张图秒懂环形链表 II（Python/Java/C++/C/Go/JS）
• LeetCode 142. Linked List Cycle II