链表中环的入口节点

题目描述

对于一个给定的链表，返回环的入口节点，如果没有环，返回null
拓展：
你能给出不利用额外空间的解法么？

题解

快慢指针。设head为A，入环点为B，相遇点为C， AB=a, BC=b, CB=c。两者第一次相遇是快指针走了a+b+c+b，慢指针走了a+b，程序使用的快指针的速度是慢指针的2倍，所以
a+b+n(c+b)=2(a+b)，所以再用一个指针从head开始步长加1的开始，另一个指针从第一次相遇的位置开始步长加1继续走，相遇的位置就是入环的位置。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast != NULL && fast->next != NULL) {
            fast = fast->next->next;
            slow = slow->next;
            if (slow == fast) {
                fast = head;
                while (slow != fast) {
                    slow = slow->next;
                    fast = fast->next;
                }
                return slow;
            }
        }
        return NULL;  
    }
};