leetcode 141 142 列表成环问题

Posted by kele on April 1, 2019

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,设 ad 距离为 x,设 dg 的距离为 y,gd 的距离为 z,则:

慢指针的移动距离为 $x+y$
快指针的移动距离为 $x+y+z+y$ 同时因为快指针比慢指针速度快一倍,所以快指针的移动距离是慢指针的两倍:

得到 $x=z$ ,也就是说ad 距离等于gd 的距离,所以只需要找一个指针从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;
    }
};