带环链表找入环结点及结论证明-1.带环链表

时间:2024-10-05 12:13:48

1.1 带环链表介绍

如下图中题目所述,带环结点尾结点的next指针域存储的可能是链表中任一结点的地址,遍历链表的时候就会死循环。

1.2 判断链表是否带环代码实现

141.环形链表(题目链接)
在这里插入图片描述
(截取部分题目描述)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
bool hasCycle(struct ListNode *head) {
    struct ListNode* fast=head,*slow=head;
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(fast==slow)
            return true;
    }
    return false;

}

1.4 入环结点相关问题

142.环形链表 II‌
在这里插入图片描述

1.4.1 结论证明

带环结点有一个经典的结论,即从快慢指针相遇点和第一个结点分别开始同步走,会在入环结点相遇。

我们假设两个指针fast, slow分别往前走,fast每次走两步,slow每次走一步,当fast入环的时候,slow大概在L/2的位置;接着,fast开始在环内不断的绕圈,当slow入环的时候,fast与slow的相对位置可能是0,1,2,3,…,C-1,因为fast走得快,所以此时转变为追击问题,fast追击slow,假设二者相对位置差N个结点,那么0=<N<=C-1.
fast每走一次,与slow的距离-1,那么走N次也就追上了,记录此时位置为meet,即相遇结点。
因为二者一直都在走,所以fast走的距离是slow的两倍。
fast走的距离为:L+X+C* n(n为正整数,因为slow走的是L+X,fast走的一定比slow快;这个n是相遇之前,fast走L+X,还走了n圈)
slow走的距离为:L+X
也即L+X+C* n=2(L+X),即L=C* n-X
我们结合下图来看上式的实际意义,让两个指针分别从相遇点和起始结点开始同时每次走一步,从头结点开始的指针走L步走到入环结点,从相遇结点开始走的指针绕环n-1圈后,再走(C-X)步到达入环结点,即从快慢指针相遇点和第一个结点分别开始同步走,会在入环结点相遇
在这里插入图片描述
在某位学长面试的时候,遇到过这样的问题:

  1. 带环链表怎么找入环结点?
  2. 为什么slow一次走一步,fast一次走2步,它们会相遇吗?会不会错过?
  3. 如果slow走1步,fast走X步(X>2),它们会相遇吗?会不会错过?以及,slow走2步的情况呢?
  4. 求环的长度(找到相遇结点后,再次从相遇结点走一周,就是环的长度)

问题1的代码实现如下,问题2已证明,我们来看问题3.
假设slow每次走1步,fast走3步,当fast入环的时候,slow大概在L/3的位置;接着,fast开始在环内不断的绕圈,当slow入环的时候,fast与slow的相对位置可能是0,1,2,3,…,C-1,因为fast走得快,所以此时转变为追击问题,fast追击slow,假设二者相对位置差N个结点,那么0=<N<=C-1.
fast每走一次,与slow的距离-2,如果N是偶数的话,那么走N/2次也就追上了;如果N是奇数的话,fast与slow的距离就逐渐变化,即N, N-3, N-5,…,1,-1.fast追击slow,那么fast与slow相对距离为-1,也就是fast超过slow,如下图所示。因为fast比slow走得快,那么此时开始新一轮的追击,如果C-1为偶数,可以追上;如果C-1为奇数,C-1是二者的相对距离,相当于N为奇数,最后二者相对距离是-1,也就是C-1,那么这样往复循环,永远追不上。
在这里插入图片描述
而fast走4步,slow每次走1步,我们考虑slow入环的时候二者相对距离N是3的倍数、N=3n+1、N=3n+2的情况;对于N=3n+1,我们要考虑C-1的情况,以此类推。
在这里插入图片描述

1.4.2 找入环结点代码实现

1.4.2.1 代码实现1
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast=head,*slow=head;
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(fast==slow)
        {
            struct ListNode* meet=slow;
            struct ListNode* start=head;
            while(meet!=start)
            {
                meet=meet->next;
                start=start->next;
            }
            return meet;
        }
    }
    return NULL;
}
1.4.2.2 代码实现2

第二种思路是,找到相遇结点,将该结点与后续结点断开,成为找两个链表的交点问题,该问题的代码在系列文章中,下面为链接,有兴趣的友友可以看一下。
链表OJ经典题目及思路总结(一)双指针
在这里插入图片描述

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode * tailA=headA,*tailB=headB;
    int lenA=1,lenB=1;
    while(tailA->next)
    {
        lenA++;
        tailA=tailA->next;
    }
    while(tailB->next)
    {
        lenB++;
        tailB=tailB->next;
    }
    if(tailA!=tailB)
        return NULL;
    int gap=abs(lenA-lenB);
    struct ListNode * longlist=headA,*shortlist=headB;
    if(lenA<lenB)
    {
        longlist=headB;
        shortlist=headA;
    }
    while(gap--)
        longlist=longlist->next;
    while(longlist!=shortlist)
    {
        longlist=longlist->next;
        shortlist=shortlist->next;
    }
    return longlist;
}
struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast=head,*slow=head;
    while(fast && fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(fast==slow)
        {
        	//转换成lt1与lt2求交点
            struct ListNode* lt1=slow->next;
            slow->next=NULL;
            struct ListNode* lt2=head;
            return getIntersectionNode(lt1,lt2);
        }
    }
    return NULL;
}