剑指offer55:链表中环的入口结点

2019-08-29 08:55:30来源:博客园 阅读 ()

新老客户大回馈,云服务器低至5折

剑指offer55:链表中环的入口结点

1 题目描述

  给一个链表,若其中包含环,请找出该链表的环的入口结点,否则,输出null。

2 思路和方法

  这是一个典型的链表中查找环的问题,基本思路是,首先设置两个快慢指针slow和fast,并且快指针fast每次前进两步,慢指针slow每次前进一步,假定当相遇的时候,设慢指针在环中走了k步,设环之外的部分长为x,环的长度

为c,则快指针一共走了:x+b1c+k步,(b1?为快指针在环中走的圈数)慢指针一共走了:x+b2c+k步,(b2?为快指针在环中走的圈数)因为快指针的速度是慢指针的两倍。

  那么可以得到:

    2(x+b2c+k)==x+b1c+k;  得到xmck

  其中m=b12b2m=b1?2b2?,慢指针在圈中还剩下的步数ck。我们可以发现,如果此时让快指针设置为从原点开始,每次只前进一步,那么由于x为mck,慢指针剩下的步数也只剩ck,这样,如果两个指针同时出发的话,

最终一定会相遇的。这时,慢指针有可能已经走了m-1圈,并在环的入口处和快指针相撞,此时求出该相遇的点即可。

3 C++核心代码

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6         val(x), next(NULL) {
 7     }
 8 };
 9 */
10 class Solution {
11 public:
12     ListNode* EntryNodeOfLoop(ListNode* pHead)
13     {
14         if(pHead==NULL||pHead->next==NULL)
15         {
16             return NULL;
17         }
18         ListNode* slow=pHead;
19         ListNode* fast=pHead;
20         while(fast!=NULL&&fast->next!=NULL)
21         {
22             slow=slow->next;
23             fast=fast->next->next;
24             if(slow==fast)
25             {
26                 fast=pHead;
27                 while(fast!=slow)
28                 {
29                     fast=fast->next;
30                     slow=slow->next;
31                 }
32                 if(fast==slow)
33                 {
34                     return slow;
35                 }
36             }
37         }
38         return NULL;
39     }
40 };
View Code

参考资料

https://blog.csdn.net/qq_29462849/article/details/90400558


原文链接:https://www.cnblogs.com/wxwhnu/p/11429099.html
如有疑问请与原作者联系

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:Java 操作Word书签(三):用文本、图片、表格替换书签

下一篇:剑指offer44:翻转单词顺序列