leetcode 141 142. Linked List Cycle

题目描述：

不用辅助空间判断，链表中是否有环

/**

 * Definition for singly-linked list.

 * struct ListNode {

 *     int val;

 *     ListNode *next;

 *     ListNode(int x) : val(x), next(NULL) {}

 * };

 */

 /*一个指针走的快  一个指针走得慢*/

class Solution {

public:

    bool hasCycle(ListNode *head) {

        if(head == NULL)

            return false;

        ListNode *first = head;

        ListNode *Second = head;

        while(Second->next != NULL){

            first = first->next;

            Second = Second->next->next;

            if(Second == NULL)

                return false;

            if(Second == first)

                return true;

        }

        return false;

    }

};

142  找到环开始的结点

第一次相遇时slow走过的距离：a+b，fast走过的距离：a+b+c+b。

因为fast的速度是slow的两倍，所以fast走的距离是slow的两倍，有 2(a+b) = a+b+c+b，可以得到a=c（这个结论很重要！）。

/**

 * 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) {

        if(head == NULL)

            return NULL;

        ListNode *first = head;

        ListNode *second = head;

        bool flag = true;

        while(second->next != NULL){

            first = first->next;

            second = second->next->next;

            if(second == NULL)

                return NULL;

            if(first == second){

                flag = false;

                break;

            }

        }

        if(flag == true)

            return NULL;

        first = head;

        while(first != second){

            first = first->next;

            second = second->next;

        }

        return first;

    }

};