环形链表问题的证明

一、说明

LeetCode上有这样两道关于环形链表的题目:

  • No.141 描述:给定一个链表,判断链表中是否有环。题目链接

  • No.142 描述:给定一个链表,返回链表开始入环的第一个节点。题目链接

这篇文章主要做一下解题方法—-快慢指针法的正确性证明。

二、证明

1.证明快慢指针在环中是可以恰好相遇的

设链表的头结点为$x_0$,环的起始结点为$x_s$,环的结点个数为$l$。当我们从$x_0$开始遍历链表的话可以得到下面的一个无穷序列:

假设$j$是$l$的整数倍且是满足$j>s$的最小的那一个,对于任意的正整数$k(k\geq2)$,考虑两个结点位置(即慢指针走到了,快指针走到了),容易知道的事实是:肯定在环中。那么也在环中,因为,可以认为是从开始多走了$k-1$个$j$步,所以

综上,两个指针一定会恰好相遇

那么为了以最快的速度让两个指针相遇,我们应该让$k​$尽可能小,所以$k​$取2。所以让慢指针走1步,而快指针走2步

2.解题代码

  • 其他题目的代码(C++, Java, Python),包括一些经典数据结构和算法的实现也放在了我的GitHub上。

2.1.第一题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
ListNode* slow = head; //慢指针
ListNode* fast = head; //快指针
while(slow != NULL && fast != NULL && fast->next != NULL){
slow = slow->next;
fast = fast->next->next; //快指针走两步
if(slow == fast)
return true;
}
return false;
}
};

2.2.第二题代码

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
28
/**
* 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* slow = head;
ListNode* fast = head;
while(fast != NULL && fast->next !=NULL){
slow = slow->next;
fast = fast->next->next;
if(slow == fast){
fast = head;
while(fast != slow){
fast = fast->next;
slow = slow->next;
}
return slow;
}
}
return NULL;
}
};
------------- 本文结束 感谢您的阅读 -------------

本文标题:环形链表问题的证明

文章作者:Perry

发布时间:2019年03月15日 - 00:15

最后更新:2019年09月19日 - 13:47

原始链接:https://perry96.com/archives/6bee53c1.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

0%