leetcode 141 142 列表成环问题

leetcode 141 判断列表是否有环

列表的题目好多都是利用快慢指针来进行的，这个也不例外
分别设置一个快指针，一个慢指针，快指针每次走两步，慢指针每次走一步，假如慢指针最终和快指针相遇，则证明有环

/**
 * 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) {
        ListNode* slow=head,*fast=head;
        while(fast&&fast->next){
            slow=slow->next;
            fast=fast->next->next;
            if(slow==fast)
            {
                return true;
            }
        }
        return false;
    }
};

leetcode 142 找出环的位置来

1. 首先我们判断是否有环，利用快慢指针可以很容易做到
2. 找到之后我们判断环的位置

假设上图快慢指针相遇点时 g，成环的位置在 d,设 a 到 d 距离为 x，设 d 到 g 的距离为 y,g 到 d 的距离为 z,则：

慢指针的移动距离为 \(x+y\)
快指针的移动距离为 \(x+y+z+y\) 同时因为快指针比慢指针速度快一倍，所以快指针的移动距离是慢指针的两倍： \[ 2(x+y)=x+y+z+y \]

得到 \(x=z\) ,也就是说a 到 d 距离等于g 到 d 的距离，所以只需要找一个指针从head，另一个指针从g 同时一步一步地遍历，就可以到达成环的位置了。

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