剑指offer 22. 链表中环的入口结点

✍个人博客：https://blog.csdn.net/Newin2020?spm=1011.2415.3001.5343
📚专栏地址：剑指offer系列题解
📝原题地址：题目地址
📣专栏定位：为找工作的小伙伴整理常考算法题解，祝大家都能成功上岸！
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

题目描述

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

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

数据范围

节点 val 值取值范围 [1,1000]。
链表长度 [0,500]。

样例

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

则输出环的入口节点3.
1
2
3
4
5
6

方法一：链表，快慢指针扫描 O(n)

这道题的思路很有趣，通过数学公式可以推出下面的结论（假设有环）：

1. 设置 slow 和 fast 指针从 head 开始往后遍历，直至 fast 和 slow 再次相遇才停止。
2. 从 head 开始往后遍历，同时 slow 继续往后遍历，直至两个指针相遇为止就是环的入口地址。

我们就拿题目的样例来举例，看看具体是如何实现的：

第一步： 设置两个快慢指针 i 和 j 。

第二步： 慢指针每次只往后走一个结点，快指针每次往后走两个结点，直至两指针相遇才停止移动。

第三步： 当两指针相遇后，再创建一个指针指向头结点，和指向当前相遇结点的指针一起往后移动，每次移动一个结点指针两结点相遇，再次相遇的结点就是该链表的入口结点。

第四步： 返回入口结点，即结点 3 。

注意：如果该链表没有入口结点，则快指针会直接遍历到空结点去，导致循环中断，这时直接返回 NULL 即该链表没有入口结点。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* entryNodeOfLoop(ListNode* head) {
        ListNode* slow = head, * fast = head;
        while (fast != NULL) {
            if (fast->next == NULL)    return NULL;
            fast = fast->next->next;
            slow = slow->next;

            if (fast == slow) {
                ListNode* cur = head;
                while (cur != slow) {
                    slow = slow->next;
                    cur = cur->next;
                }
                return cur;
            }
        }
        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

欢迎大家在评论区交流~