快慢指针
# 快慢指针
# 142 环形链表 II (opens new window)
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 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 反转链表 (opens new window)
给定单链表的头节点 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 个结点 (opens new window)
给定一个链表,删除链表的倒数第 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 cnt = 0;
while(cnt < n+1){
fast = fast->next;
++cnt;
}
// 慢指针 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;
}
};