每日一题---OJ题: 环形链表 II

片头

嗨! 小伙伴们,大家好! 我们又见面啦,在上一篇中,我们学习了环形链表I, 今天我们继续来打boss,准备好了吗? Ready Go ! ! !

emmm,同样都是环形链表,有什么不一样的地方呢?

肯定有, 要不然也不会一个标记为"简单" ,一个标记为"中等"了,哈哈哈哈哈

让我们分析一下题目,哦~,原来是要返回链表开始入环的第一个结点呀! 上一个题目只是让我们简单的判断一下链表中是否有环,看来这次要求比上一次更高了,不怕不怕,一起来做一做~~~

举个例子:

在上图中,总共有4个结点,分别为 3, 2, 0, -4, 链表中有一个环,尾结点连接到第二个结点,返回第二个结点。

上图中,总共有2个结点, 分别为 1, 2, 链表中有一个环,尾结点连接到第一个结点,返回第一个结点。

上图中，只有1个结点，链表没有环，返回NULL

针对这道题,有两种思路,我们一起来看看吧!

思路一: 我们定义两个指针,分别为 fast 和 slow指针, slow指针每次走1步,fast指针每次走2步,利用 fast 和 slow 之间的数学逻辑关系,来解答此题。

当slow指针走到中间的时候,fast指针开始进环

链表头->入口点: L

当slow指针开始进环的时候,fast指针在环中可能已经走了n圈了

此时,fast指针和slow指针都在环里面,slow指针进环以后开始追击。在上一章中，我们知道，当fast和slow之间的速度只相差1个单位的时候,fast指针一定能追上slow，最终两指针相遇。

链表头->入口点: L

入口点->相遇点: X

环的长度: C

追上相遇时: slow走的距离: L+X

追上相遇时: fast走的距离: L+ n*C + X (假设fast追上slow时,转了n圈 (n>=1))

思考: slow有没有可能转了超过1圈? 没有! 因为slow都走了一圈了,那么fast走了2圈了,早追上了。

fast 追上slow时，fast走的距离是slow的2倍,我们可以列一个等式:

2*(L+X) = L + n*C + X

L+X = n*C

L = n*C - X

哈哈哈,重头戏来咯! 我们可以得到一个结论: 一个指针从链表头开始走,一个指针从相遇点开始走,它们都以相同的速度(每次一步)进行移动,最终它们会在入口点相遇。

所以,基于这个结论,这道题的代码如下:

  typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
        ListNode* fast = head;      //初始时,定义一个fast指针指向头结点
        ListNode* slow = head;      //初始时,定义一个slow指针指向头结点
        while(fast && fast->next)   //当fast为空或者fast->next为空,则跳出循环
        {
            fast = fast->next->next;//fast每次走2步
            slow = slow->next;      //slow每次走1步
            if(fast == slow)        //如果fast和slow相遇
            {
                ListNode* meet = slow;//定义一个meet结点,用来找入口点
                while(meet != head)   //只有当两个指针再次相遇,循环才结束
                {
                    meet = meet->next;//meet每次走一步
                    head = head->next;//head每次走一步
                }
                return meet;          //当两个指针再次相遇时,即入环的第一个结点
            }
        }
        return NULL;            //如果fast为空或者fast->next为空,说明链表里面没有环
}

emmm,有的小伙伴会这样说: 哎呀,我想不起来这个推导过程以及结论,有没有其他的思路?

当然有! 且听我慢慢道来~

思路二: 我们定义两个指针,分别为 fast 和 slow指针, slow 指针每次走1步, fast 指针每次走2步, 当它们第一次相遇的时候,我们就把这个环断开,变成两个单链表,查找相交结点。

嗯，有点不太好理解，咱们画个图吧！

上图中，总共有8个结点，分别为 a1, a2, b1, b2, b3, c1, c2, c3 ,链表中有一个环,由 c3 结点指向 b1 结点, 题目要求我们把第一个相交结点(也就是 c1 结点)返回。

同理，我们先让fast指针每次走2步,slow指针每次走1步,它们最终会在 b2 结点相遇。

第一次:

第二次:

第三次:

第四次:

第五次:

第六次:

当快慢指针第一次相遇时，我们用meet结点来代表它们相遇的结点。用meet结点的next指针(meet->next)指向headx结点,随后meet结点的next指针指向NULL。

也就变成了这样：

变成了2个单链表，分别是 a1->a2->c1->c2->c3->b1->b2 和 b3->c1->c2->c3->b1->b2

现在我们需要求两个单链表第一次相交的结点,哈哈哈,求链表开始入环的第一个结点瞬间变成了求两个单链表的第一次相交的交点,好神奇~

注意: 小伙伴们如果不会求两个链表相交的起始结点,可以参考这篇文章相交链表(点击蓝色字体可以跳转相应的文章)

整体代码如下:

   typedef struct ListNode ListNode;
 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB){
        ListNode* pA = headA;   //pA指针指向头结点(链表头)
        ListNode* pB = headB;   //pB指针指向头结点(链表头)

        int lenA = 0;           //统计链表A的长度
        while(pA->next != NULL) //查找链表A的尾结点
        {
            pA = pA->next;      //pA会一直遍历到尾结点      
            lenA++;             //每走过一个结点,链表A的长度自增一次        
        }
        lenA = lenA + 1;        //不要忘了尾结点

        int lenB = 0;           //统计链表B的长度
        while(pB->next != NULL) //查找链表B的尾结点
        {
            pB = pB->next;      //pB会一直遍历到尾结点      
            lenB++;             //每走过一个结点,链表A的长度自增一次        
        }
        lenB = lenB + 1;         //不要忘了尾结点

        if(pA != pB){            //如果尾结点不相同,说明链表A和链表B根本不会相交
            return NULL;         //返回NULL
        }

         //求链表A和链表B的长度差
        int gap =abs(lenA-lenB);       
        //假设链表A的长度比链表B短,那么将A链表定义为shortList
        ListNode* shortList = headA; 
      //假设链表B的长度比链表A长,那么将B链表定义为longList   
        ListNode* longList = headB;   
        if(lenA > lenB)
        {                               //如果链表A的长度大于链表B
            shortList = headB;          //将链表B定义为shortList
            longList = headA;           //将链表A定义为longList
        }
        while(gap--){                   //让长的链表先走长度差
            longList = longList->next;  
        }

        //现在长的链表和短的链表起始位置和尾结点的距离相同
        //让他们每一个结点依次比较,直到找到第一个相同的结点为止(也就是交点)
        while(shortList != longList)    
        {
            longList = longList->next;
            shortList = shortList->next;
        }
        return shortList;   //找到交点了,将这个结点返回
 }

struct ListNode *detectCycle(struct ListNode *head) {
       ListNode* fast = head;                //定义一个fast指针,指向链表头
       ListNode* slow = head;                //定义一个slow指针,指向链表头
       while(fast && fast->next)             //当fast为空或者fast->next为空时,退出循环
       {
            fast = fast->next->next;         //fast指针每次走2步 
            slow = slow->next;               //slow指针每次走1步
            if(fast == slow)                 //如果fast指针和slow指针第一次相遇
            {
         //定义一个变量meet,用来保存它们第一次相遇的结点
                ListNode* meet = slow;   
        //定义一个变量headx,将meet的next指针指向headx
                ListNode* headx = meet->next;
        //将meet结点的next指针置为NULL
                meet->next = NULL;        

                return getIntersectionNode(head,headx);//将找到的相交结点返回
            }
       }
       return NULL;  //如果fast为空,或者fast->next为空,说明链表没有成环,返回NULL
}