题目

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

数据范围： n\le10000n≤10000，1<=结点值<=100001<=结点值<=10000
要求：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

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

可以看到环的入口结点的结点值为3，所以返回结点值为3的结点。
输入描述：
输入分为2段，第一段是入环前的链表部分，第二段是链表环的部分，后台会根据第二段是否为空将这两段组装成一个无环或者有环单链表
返回值描述：
返回链表的环的入口结点即可，我们后台程序会打印这个结点对应的结点值；若没有，则返回对应编程语言的空结点即可。

示例1
输入：{1,2},{3,4,5}
返回值：3

说明： 返回环形链表入口结点，我们后台程序会打印该环形链表入口结点对应的结点值，即3

示例2
输入：{1},{}
返回值：“null”

说明： 没有环，返回对应编程语言的空结点，后台程序会打印"null"

示例3
输入：{},{2}
返回值：2

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

解决

步骤思路：

1.判断该链表是否有环 先解决该问题BM6 判断链表中是否有环

环形链表的环一定在末尾，末尾没有NULL了。
如果是普通线形链表末尾一定有NULL，那我们可以根据链表中是否有NULL判断是不是有环。

2.在有环的链表中找到环的入口

哈希表

思路

遍历链表节点，每遍历一次存进哈希表一次，如果哈希表第一次重复存入一个节点，该节点为环的入口节点。

步骤

1.判断该链表是否为空
2.创建哈希表
3.遍历该链表，如果当前节点没有在哈希表里，继续遍历下一个。直到有一个节点已经存在在哈希表中，该节点就是环的入口节点。

代码实现

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        //判断链表是否为空
        if(pHead==NULL)
            return NULL;        
        //创建哈希表
        unordered_set<ListNode *>setlist;
        //遍历链表
        while(pHead)
        {
            //容器内已存在该节点：该节点为环的入口节点
            if(setlist.count(pHead)==1)//容器内已存在该节点：该节点为环的入口节点
            {
                return pHead;
            }
            else
            {
                setlist.insert(pHead);
                pHead=pHead->next;
            }
        }
        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
24
25
26
27
28
29
30
31
32
33
34

双指针法

思路

创建两个指针，一个快指针每次偏移两个节点，一个慢指针每次偏移一个节点，如果遍历快指针永远不为null，则该链表有环。
确定该链表一定有环时，两指针继续偏移，两指针最后一定会在环内相遇，此时慢指针一定没有将整条链表遍历完。
指针相遇时，快指针立刻指向头节点，且偏移步幅改为1，慢指针保持原步幅继续偏移。经过下图分析，当两个指针再次相遇，相遇的节点就是环的入口节点。
头节点到入口节点=（k-1）圈环长度+相遇节点到入口节点

步骤

1.封装一个函数判断该链表是否有环 【牛客题霸】链表05-BM6 判断链表中是否有环（稍作修改，如果有环则返回两指针相遇节点）
2.封装获取换入口节点函数。调用链表是否有环函数判断该链表是否有环。
3.无环：返回null，结束函数。
4.有环：创建一个指针接收返回的相遇的节点。创建fast指针指向链表头节点。两节点遍历链表，步幅为1，则两指针相遇节点一定是环的入口节点。返回该节点即可。

代码实现

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    //创建判断链表是否有环函数
    ListNode* iscycle(ListNode* pHead)
    {
        //判断俩表是否为空
        if(pHead==NULL)
        {
            return NULL;
        }
        //创建快慢指针，初始都指向头节点
        ListNode *fast=pHead;
        ListNode *slow=pHead;
        //遍历链表
        while(fast!=NULL&&fast->next!=NULL)
        {
            fast=fast->next->next;
            slow=slow->next;
            //如果两指针相遇，返回相遇的节点
            if(fast==slow)
            {
                return slow;
            }
        }
        //遍历到链表末尾指向NULL：表示该链表没有环，返回NULL
        return NULL;
    }
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        //判断该链表是否有环
        ListNode *slow=iscycle(pHead);
        //无环，退出
        if(slow==NULL)
        {
            return NULL;
        }
        //有环，得到快慢指针相遇节点
        //创建快指针指向头结点
        ListNode *fast=pHead;
        //两指针遍历链表，慢指针从相遇节点开始向后偏移，快指针从头结点向后偏移
        while(fast!=slow)
        {
            fast=fast->next;
            slow=slow->next;
        }
        //两指针相遇的节点就是环的入口节点，返回该节点
        return slow;
    }
};
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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57