手机版 欢迎访问it开发者社区(www.mfbz.cn)网站

当前位置: > 开发

LK141142-环形链表

时间:2021/5/31 21:57:04|来源:|点击: 次

LK141-环形链表

https://leetcode-cn.com/problems/linked-list-cycle/description/

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;
    }
};

 

LK142-环形链表2

https://leetcode-cn.com/problems/linked-list-cycle-ii/description/

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode*slow=head,*fast=head;
        while(fast&&fast->next){
            slow=slow->next;
            fast=fast->next->next;
            //slow==fast说明fast追上了slow证明链表有环
            if(slow==fast){
                //meet为slow和fast的相遇点
                ListNode*meet=fast;
                while(head!=meet){
                    head=head->next;
                    meet=meet->next;
                }
                return meet;//此时meet为入环的第一个节点
            }
        }
        //fast==nullptr||fast->next==nullptr说明链表不带环
        return nullptr;
    }
};

1.判断链表是否带环?

-快慢指针-slow一次走一步,fast一次走两步,如果链表有环,fast一定会在环内追上slow

 

2.证明slow一次走一步,fast一次走两步,fast一定能追上?

假设slow刚入环和fast距离为N

slow一次走一步,fast一次走两步,每各走一步,slow和fast之间的距离减小1

N-1

N-2

...

N-N=0

最后一定会减到0

 

3.如果slow一次走一步,fast一次走3步呢?fast一次走4步呢?

如果fast一次走3步,那么每各走一步,slow和fast之间的距离减小2

N-2

N-4

...

如果N为奇数,最后相减N为-1

极端情况下,N每次都为奇数,那么slow和fast永远不会相遇

如果fast一次走4步,那么每各走一步,slow和fast之间的距离减小3

N-3

N-6

N-9

...

极端情况下,N每次都刚好错开,那么slow和fast永远不会相遇

 

4.若带环,求出环的长度?-从相遇点再走一圈

 

5.若带环,求出环的入口点?

head-头节点

entry-环的入口点

meet-slow和fast的相遇点

假设

head->entry:L

环:C

entry->meet:X

因为slow走一步,fast走两步,所以到相遇时fast走的距离是slow的2倍

2(L+X)=L+NC+X

L+X=NC

L=NC-X

所以head和meet同时走,会在entry相遇

上一篇:PPT学习资源(总) 下一篇:Atcode abc203 CD

Copyright © 2002-2019 某某自媒体运营 版权所有