「转载」快慢指针法-解决环形链表类题目

发表于 更新于 Artalk： loading...

前言

转载自kirsche在 leetcode-cn 142.的题解

经典题目，142.环形链表Ⅱ

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

image-20210915213946812

一般用快慢指针来解决此类问题，例如寻找距离尾部第K个节点、寻找环入口、寻找公共尾部入口等。

算法思路

假设链表有环，fast和slow从head出发，fast指针一次前进两步，slow指针一次前进一步，因为有速度差，最终两指针一定会在环中相遇。

1、两个指针第一次相遇

设链表共有a+b个节点（环上b个），假设两指针相遇时，fast走了f步，slow走了s步，则有如下关系：

  • f=2sf=2s
  • f{f}-s=nb{s}=nb ，即fast比slow多走了n倍的环的长度

化简以上两式，s=nbs=nb，即slow走了n倍的环周长

image-20210915220020400

2、如何得出环的入口节点？

每一次走道环的入口节点，走过的步数都满足k=a+nbk=a+nb，而此时slow指针已经走了nb，也就是说slow指针再走a步，则一定位于环的入口节点。

3、让fast和slow第二次相遇

如何能让slow指针精准走a步呢？

答：令fast从head重新出发，slow从之前相遇点出发。此时f=0f=0，s=nbs=nb。当f=af=a, s=a+nbs=a+nb时，此时两指针再次相遇，并且都指向环的入口节点；

代码

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
26
27
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head, *slow = head;
        
        while (1){
            if (fast == NULL || fast->next == NULL) return NULL;
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow) break;
        }
        fast = head;
        while (fast != slow){
            fast = fast->next;
            slow = slow->next;
        }
        return fast;
    }
};

其它例题

剑指 Offer II 021. 删除链表的倒数第 n 个结点

问题描述：

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

示例：

img

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

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        // 快慢指针
        ListNode *p = new ListNode(); p->next = head;
        ListNode *fast = p, *slow = p;
        while (n --) {
            fast = fast->next;
        }
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next;
        }
        slow->next = slow->next->next;
        return p->next;
    }
};

以上代码中，利用了前置哨兵节点p，是针对“删除首节点的情况”。

📔博文图谱

提及本博文的链接