LeetCode刷题笔记双指针快慢指针

编程入门行业动态更新时间:2024-10-24 01:55:27

快慢指针

快慢指针 Equi-directional：两个指针指向同一线性表，遍历方向相同，且两个指针起点可以相同，也可以不同形成一个滑动窗口，两个指针以不同的策略移动，直到两个指针的值相等或满足其他特殊条件为止。

142 环形链表 II

给定一个链表，返回链表开始入环的第一个节点。如果链表无环，则返回 null。

输入是一个链表，输出是链表的一个节点，如果没有环路，返回一个空指针。

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

解析：

通常使用 Floyd 判圈法，解决链表找环路的问题。其基本思路就是使用快慢指针，快指针一次走两步，慢指针一次走一步，如果这两个指针会相遇则说明存在环路。现在再用一个指针从链表头节点开始一次走一步，慢指针从两个指针相遇的点开始继续一次一步往前走，当这两个指针相遇时，就是环路的入口。

根据上述思路，我们给定两个指针，分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步：

如果 fast可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻 slow 和 fast 相遇。

如果存在环路，当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。

class Solution {
public:ListNode *detectCycle(ListNode *head) {ListNode *fast = head, *slow = head;do{if(!fast || !fast->next){return nullptr;}fast = fast->next->next;slow = slow->next;}while(slow != fast);fast = head;while(slow != fast){slow = slow->next;fast = fast->next;}return fast;}
};

206 反转链表

给定单链表的头节点 head ，请反转链表，并返回反转后的链表

输入一个链表，输出一个反转后的链表

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

解析：

反转链表是快慢指针的经典应用场景。

为了便于统一节点处理方式，我们在链表中加入一个虚拟头节点dummy，其 next 指向链表头节点。然后我们给定两个指针 slow 和 fast，初始时分别指向 dummy 和链表头节点。然后我们进行反转操作：

首先使用 tmp 保存 fast 的 next 指向的节点反转 fast 的 next 指向，指向前一节点即 slow移动 slow 到当前 fast更新 fast 指向为其原始 next 指向节点，即 tmp 保存的节点

class Solution {
public:ListNode* reverseList(ListNode* head) {ListNode *slow = nullptr, *fast = head;while(fast){// 为了便于理解，我还是新建了 tmp。当然你可以直接使用闲置的 head 记录，节省空间开销ListNode* tmp = fast->next;fast->next = slow;slow = fast;fast = tmp;} return slow;}
};

19 删除链表的倒数第 N 个结点

给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

输入一个链表，输出一个按条件操作之后的链表

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

解析：

对于本题首先我们来考虑删除链表的第 N 个节点怎么操作。我们可以使用一个指针从头节点开始遍历找到链表的第 N-1 个节点，然后改变其 next 指向为 next->next ，最后删除第 N 个节点即可。

那么我们怎么删除倒数第 N 个节点呢？我们要找到倒数第 N 个节点的前一个节点。假设链表总共有 M 个节点，那么倒数第 N 个节点就是第 M - N 个节点。

所以我们可以使用快慢指针，快指针 fast 先遍历到链表的第 N 个节点，此时慢指针 slow 再出发与 fast 同步移动。当 fast 遍历完链表最后一个节点时，slow 指向的就是倒数第 N 个节点。

为了便于删除操作，我们让 fast 先遍历到第 N+1 个节点，这时当 fast 遍历完时，slow 指向就是倒数第 N+1 个节点，即待删除节点的前一个节点。

值得注意的是，我们定义一个虚拟头节点指向链表的头节点，这样同一的对头节点的删除操作。

class Solution {
public:ListNode* removeNthFromEnd(ListNode* head, int n) {// 创建虚拟头节点ListNode* dummy = new ListNode(0,head);ListNode *slow = dummy, *fast = dummy;// 让 fast 先遍历到第 N+1 个节点int t = 0;while(t < n+1){fast = fast->next;++t;}// 慢指针 slow 与 fast 同步移动到第 N+1 个节点while(fast){fast = fast->next;slow = slow->next;}// 删除第 N 个节点ListNode* tmp = slow->next;slow->next = slow->next->next;delete(tmp);return dummy->next;}
};