链表中环的入口结点

发表于 更新于 分类于 本文字数： 825 阅读时长 ≈ 3 分钟

JZ23 链表中环的入口结点

描述

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： $n≤10000，1<=结点值<=10000$

要求：空间复杂度 $O(1)$，时间复杂度 $O(n)$

例如，输入{1,2},{3,4,5}时，对应的环形链表如下图所示：

img

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。

输入描述：

输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表

返回值描述：

返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

示例1

1
2
3
输入：{1,2},{3,4,5}
返回值：3
说明：返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3

示例2

1
2
3
输入：{1},{}
返回值："null"
说明：没有环，返回对应编程语言的空结点，后台程序会打印"null"

示例3

1
2
3
输入：{},{2}
返回值：2
说明：环的部分只有一个结点，所以返回该环形链表入口结点，后台程序打印该结点对应的结点值，即2

题解

初见思路：和JZ52相似，题目确定环一定在尾部，我们所需要的就是首先确定链表长度，其次确定环的长度。

补充：由于不确定有没有环，所以首先可以使用快慢指针确定有没有环。利用此时的快慢指针可以判断环的长度？

最终题解：我的思路是正确的，后续还要继续拓展。这道题就是用快慢指针来做的，首先快慢指针确定有没有环是正确的，其次要标记相遇点，然后另一个指针标记头部，二者同时出发，再次相遇时即为环的入口。具体推导如下

推导

假设非环部分长度$L$，环总长$C$，第一次相遇至环入口的距离$F$（按行走的方向计算），第一次相遇点$meet$

二者相遇时：

慢指针走了$S = L+F$，而快指针走了$2S = 2(L+F)$，快指针至少多饶了一圈，从而有$2(L+F) = L+F+n \times C \rightarrow L+F=n \times C $，其中$n$是快指针多绕的圈数。

从而有$L = n\times C -F = (C-F)+(n-1)\times C$

也就是说

  • 从头到环的入口的距离$L$，等于环中从第一次相遇点到环入口的剩余距离$(C-F)$，加上若干整圈的环长度$(n-1)\times C$.
  • 也就是说，如果从头开始走$L$步，同时从相遇点沿环走$L$步，二者一定在环的入口处相遇。
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
29
30
31
32
33

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast)
                break;
        }

        if(fast==NULL)
            return NULL;
        ListNode* meet = slow;
        ListNode* head = pHead;
        while(meet!=head){
            meet = meet->next;
            head = head->next;
        }
        return meet;
    }
};