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相遇