leetcode 面试题 02.08. 环路检测

待我称王封你为后i 2023-01-15 15:25 96阅读 0赞

[https://leetcode-cn.com/problems/linked-list-cycle-lcci/solution/huan-lu-jian-ce-by-leetcode-solution-s2la/][https_leetcode-cn.com_problems_linked-list-cycle-lcci_solution_huan-lu-jian-ce-by-leetcode-solution-s2la]

法1：hash

法二 快慢指针：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]

一个快指针f 每次走两步
    一个慢指针l 每次走一步
    
    当他们第一次相遇的时候，快指针与慢指针都过了a，
    并且快的比慢的多走了n个b，n是整数
    由于
    
    因为两者速度差值和l的速度是一样的
    重点是，此时l也走了n个b的长度，虽然可能不在环的入口
    这个时候需要把l走到环的入口
    就让l再走a即可
    所以让一个指针在head的地方和l一起走
    然后相遇的时候就是入口了

class Solution { 
    public:
        ListNode *detectCycle(ListNode *head) { 
            
            bool cy = false;
            
            auto f = head;
            auto l = head;
            while(f!=nullptr && f->next!=nullptr){ 
                f = f->next->next;
                l = l->next;
                if(f == l){ 
                    cy = true;
                    break;
                }
            }
            
            if(!cy){ 
                return nullptr;
            }
            
            f = head;
            while(true){ 
                
                if(f == l){ 
                    break;
                }
                
                f = f->next;
                l = l->next;
                
            }
            return l;
        }
    };

![在这里插入图片描述][20210423095308803.png]

[https_leetcode-cn.com_problems_linked-list-cycle-lcci_solution_huan-lu-jian-ce-by-leetcode-solution-s2la]: https://leetcode-cn.com/problems/linked-list-cycle-lcci/solution/huan-lu-jian-ce-by-leetcode-solution-s2la/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0wxNTU4MTk4NzI3_size_16_color_FFFFFF_t_70]: /images/20221022/531dcdf8235741c08ae4f0ecc78c9129.png
[20210423095308803.png]: /images/20221022/bcb1789ac8734cc891c244476a19907b.png