题目描述
给定一个链表，若其中包含环，则输出环的入口节点。
若其中不包含环，则输出
null。
数据范围
节点 val 值取值范围 [1,1000]。
链表长度 [0,500]。
样例
给定如上所示的链表： [1, 2, 3, 4, 5, 6] 2 注意，这里的2表示编号是2的节点，节点编号从0开始。所以编号是2的节点就是val等于3的节点。 则输出环的入口节点3.
方法一：链表，快慢指针扫描 O(n)
这道题的思路很有趣，通过数学公式可以推出下面的结论（假设有环）：
设置 slow 和 fast 指针从 head 开始往后遍历，直至 fast 和 slow 再次相遇才停止。
从 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; } };
欢迎大家在评论区交流~
