环形链表题解以及证明_环形链表证明

1.题目：环形链表

https://leetcode.cn/problems/linked-list-cycle/description/

给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。
注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。

思路：
快慢指针，快指针一次走两步，慢指针一次走一步，相遇即是有环，不相遇即是无环

bool hasCycle(struct ListNode *head) {
    
    //快慢指针，如果相遇则有环
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;
        if (fast == slow)
        {
            return true;
        }
    }
    return false;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

问题1：为什么快指针走两步，慢指针走一步可以？

证明：假设当慢指针走到入环口时，快指针和慢指针的相对位置如图所示：

假设此时fast和slow的距离为x(顺时针)，如果快指针走两步，慢指针走一步，他们的距离就会每次缩小1，
x
x-1
x-2
…
0
最终就会相遇

问题2.快指针走3，4…n步，慢指针走1步可以吗？

证明：快走3步，慢走一步。假设当慢指针走到入环口，快指针和慢指针相对位置如图：

假设此时fast和slow的距离为x，每走一步，他们的距离-2
x
x-2
x-4
…
此时分为两种情况：

1. 当x是2的倍数时，最终的距离为0，即fast和slow会相遇
2. 当x不是2的倍数时，fast会超过slow，假设此时环长为N，
   fast和slow的距离为N-1(顺时针)
   • 当N-1为2的倍数时，fast和slow会相遇
   • 当N-1不是2的倍数时，fast每次追上slow后他们的距离又是N-1，即：fast永远追不上slow

同理：4，5…n都是看情况，不是一定相遇
总结：

• 当快慢指针的相对速度为1时，他们一定相遇
• 其余情况，都不一定。
  

2.题目：环形链表Ⅱ

https://leetcode.cn/problems/linked-list-cycle-ii/description/

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
**不允许修改 **链表。

思路：两种思路可以解题，下面介绍思路1

1. 让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环
   运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
2. 如果可以修改链表的话，从fast和slow相遇处断开，形成两个 链表，求两个链表的第一个相交节点即可
   

struct ListNode *detectCycle(struct ListNode *head) {
    
    //思路：先计算快慢指针的相遇点，然后从链表开头和相遇点一起走，相遇点就是入环节点
    struct ListNode* fast = head;
    struct ListNode* slow = head;
    while (fast != NULL && fast->next != NULL)
    {
        fast = fast->next->next;
        slow = slow->next;

        if (fast == slow)
        {
            struct ListNode* cur = head;
            while (cur != fast)
            {
                cur = cur->next;
                fast = fast->next;
            }
            return fast;
        }
    }
    return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

问题：为什么思路1中两指针一定会在入口处相遇？
证明：相遇处的图示如下：假设环长为N，入环点到相遇点距离为x，链表头到入环点的距离为L

慢指针走的路程：S1 = L+x
快指针走的路程：S2 = L+k*(N)+x------->当环足够小时，快指针走了k圈环，k>=1
因为 ：快指针的速度是慢指针的二倍，
所以 ：2S1 = S2
于是有：2(L+x) = L + k*(N) + x
有：2*(L+x) = L + (k-1)*N + N + x
两边化解：L = (k-1)*N + N - x, -------假设slow和fast相遇点记为环中指针的出发点
当k = 1 时，L = N - x
当k = 2时， L = N + N - x， 不管k是几，环中指针每次都可以等效于从相遇点出发，走N-x路程就会和另一个指针在 入环口相遇
…
即：两指针一定会在入口点相遇