[LeetCode]142.Linked List Cycle II

题目： Given a linked list, return the node where the cycle begins. If there is no cycle, return null. Follow up: Can you solve it without using extra space?

分析：

首先使用快慢指针技巧，如果fast指针和slow指针相遇，则说明链表存在环路。当fast与slow相遇时，slow肯定没有遍历完链表，而fast已经在环内循环了n圈了（1<=n）设slow走了s步，则fast走了2s步（fast步数还等于s加上环在多转的n圈），设环长为r则：

2s = s + nrs = nr

设整个链长L，环入口点与相遇点距离为a，起点到环入口点距离为x，则：

x + a = s = nr = (n – 1)r + r = (n – 1)r + L – xx = (n – 1)r + L – x – a

L -x -a 为相遇点到环入口点的距离，由此可知，，从链表开头到环入口点等于n – 1圈内环 + 相遇点到环入口点，于是我们可以从head开始另设一个指针slow2，两个慢指针每次前进一步，他们两个一定会在环入口点相遇。

代码：

/**————————————* 日期：2015-02-05* 作者：SJF0115* 题目: 142.Linked List Cycle II* 网址：https://oj.leetcode.com/problems/linked-list-cycle-ii/* 结果：AC* 来源：LeetCode* 博客：—————————————**/;struct ListNode{int val;ListNode *next;ListNode(int x):val(x),next(NULL){}};class Solution {public:ListNode *detectCycle(ListNode *head) {if(head == nullptr){return nullptr;}//ifListNode *slow = head,*fast = head,*slow2 = head;while(fast != nullptr && fast->next != nullptr){slow = slow->next;fast = fast->next->next;// 相遇点if(slow == fast){while(slow != slow2){slow = slow->next;slow2 = slow2->next;}//whilereturn slow;}//if};}};

坚硬的城市里没有柔软的爱情，生活不是林黛玉，