AcWing 34. 链表中环的入口结点
宋标 Lv5
  2022-08-18 02:31:50 2022-08-18 02:31    

题目

给定一个链表，若其中包含环，则输出环的入口节点。

若其中不包含环，则输出null。

数据范围

节点 val 值取值范围 。
节点 val 值各不相同。
链表长度 。

样例

![QQ截图20181202023846.png][QQ_20181202023846.png]

给定如上所示的链表：
[1, 2, 3, 4, 5, 6]
2
注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。

则输出环的入口节点3.

[QQ_20181202023846.png]:

题解

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
/**/
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        auto i = head, j = head;
        while (i && j)
        {
            i = i -> next;
            j = j -> next;

            //快指针走两步
            if (j) j = j -> next;
            //不存在环
            if (!j) return 0;

            //指针相遇
            if (i == j)
            {
                //i指向起点，与j走x步直到相遇，便是环入口
                i = head;
                while(i != j)
                {
                    i = i -> next;
                    j = j -> next;
                }
                return i;
            }
        }
        return 0;
    }
};
 评论