菜鸟笔记
提升您的技术认知

环形链表问题-ag真人游戏

问题描述:
给定一个链表,判断链表中是否有环。

首先介绍一下快慢指针:
我们定义两个指针,一快一慢。慢指针每次只移动一步,而快指针每次移动两步。
来看以下例子:

在环形链表问题中,我们用slow和fast指向链表的开始,slow一次走一步,fast一次走两步。若不带环,fast就会为空,带环,fast就会在环内追上slow

1.我们先来证明为什么slow和fast一定会在环中相遇。

  1. fast先进环,这时slow走了入环前距离的一半。
  2. 随着slow进环,fast在环内走了一段,但走了多少跟环的大小有关。
  3. 假设slow进环时,与fast之间的距离是n,fast开始追slow。slow每次往前走一步,fast往前走两步。所以fast和slow的距离变化:
    n -> n-1 -> n-2 … 1 -> 0
    每追一次,距离就减1,他们之间的距离减到0的时候就是相遇的点。

那么如何求环的入口点呢?
追上相遇的过程中:

  1. slow走的距离:l x
    fast走的距离:l n* c x (n>=1)
    (n是相遇前,fast在环内走的圈数)
  2. 2*(l x) = l n* c x
    得到:l=(n-1)* c c-x
  3. 其中,(n-1)* c相当于从相遇点又走回到相遇点,没有变化, c-x 相当于从相遇点到相交点(顺时针)的距离。

结论: 一个指针从链表起始位置运行,一个指针从相遇点位置绕环,每次都走一步,两个指针最终会在入口点的位置相遇。

代码实现:

struct listnode *detectcycle(struct listnode *head) {
  
    struct listnode* slow=head,*fast=head;
    while(fast && fast->next)
    {
  
        slow=slow->next;
        fast=fast->next->next;
        if(slow == fast)
        {
  
            //相遇
            struct listnode* meet=slow;
            while(meet != head)
            {
  
                meet=meet->next;
                head=head->next;
            }
            return meet;
        }
    }
    return null;
}

或者我们可以转换成链表相交的问题,即令相遇点的下一个结点为另一个链表头,这里不再细讲。

延伸问题:证明fast一次走n步时,即n>2时不一定会在环中相遇。

假设slow一次走1步,fast一次走3步,slow进环后,fast和slow之间的距离为n,fast开始追slow。
他们之间的距离变化如下:

  1. n是偶数:
    n -> n-2 -> n-4 … 2 -> 0
    n是偶数时可以追上

  2. n是奇数:
    n -> n-2 -> n-4 … 1 -> -1
    n是奇数时,将会错过

如果n是奇数,距离变为-1,即意味着他们之间的距离变为c-1(c是环的长度)
如果c-1也是奇数,那么就永远追不上了,
如果c-1是偶数,就可以追上。

假设slow一次走1步,fast一次走n步的推导过程与之类似。

网站地图