算法进阶——链表中环的入口节点

题目

---

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

数据范围：1<=结点值<=10000

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

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

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

输入描述：

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

返回值描述：

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

示例1

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

示例2

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

示例3

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

思路

---

首先，题目中给的链表并不一定是有环的，所以需要先判断链表是否有环。可以在通过快慢指针的方式来判断，如果有环，则可以计算出环节点的个数。

然后，定义两个指针初始化指向头节点，第一个指针先前进环节点个数，之后两个节点同时前进，到节点值相等的节点就是环的入口节点。

本题还可以使用哈希表unordered_set来记录经过的节点来解决，但是这个方法的空间复杂度时O(n)。

另外，我的解法写的比较复杂，主要是为了理顺思路。使用快慢指针可以用更简洁的代码解决。

解答代码

---

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead) {
        if (pHead == nullptr || pHead->next == nullptr) {
            return nullptr;
        }

        // 获取到环节点的个数
        int loop_node_num = GetLoopNodeNum(pHead);
        if (loop_node_num == 0) {
            // 链表中没有环
            return nullptr;
        }

        ListNode* pNode1 = pHead;
        ListNode* pNode2 = pHead;
        // 第一个节点先前进loop_node_num步
        for (int i = 0; i < loop_node_num; i++) {
            pNode1 = pNode1->next;
        }

        // 两个节点同时前进
        while (pNode1->val != pNode2->val) {
            pNode1 = pNode1->next;
            pNode2 = pNode2->next;
        }

        // 相等的点就是环的入口
        return pNode1;  
    }

    int GetLoopNodeNum(ListNode* pHead) {
        int loop_node_num = 0;
        // 定义快慢指针
        ListNode* fast = pHead->next;
        ListNode* slow = pHead;

        // 判断是否有环
        bool is_loop = false;
        while (fast != nullptr) {
            if (fast->val == slow->val) {
                is_loop = true;
                break;
            } else {
                if (fast->next != nullptr) {
                    fast = fast->next->next;
                    slow = slow->next;
                } else {
                    break;
                }
            }
        }

        // 有环，则步进慢指针计算环的节点数
        if (is_loop) {
            int val = slow->val;
            loop_node_num = 1; // 加上自身
            while (val != slow->next->val) {
                ++loop_node_num;
                slow = slow->next;
            }
        }

        return loop_node_num;
    }
};
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75