博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[Leetcode] Linked list cycle ii 判断链表是否有环
阅读量:4565 次
发布时间:2019-06-08

本文共 1931 字,大约阅读时间需要 6 分钟。

Given a linked list, return the node where the cycle begins. If there is no cycle, returnnull.

Follow up:

Can you solve it without using extra space?

题意:给定链表,若是有环,则返回环开始的节点,没有则返回NULL

思路:题目分两步走,第一、判断是否有环,第二若是有,找到环的起始点。关于第一点,可以参考之前的博客 。这里主要分析在有环的情况下的第二步。

 

说明:在环中的前进方向是顺时针,起点为X,环入口为Y,相遇点在Z;无环X->Y的距离(节点数)为a,相遇点Z到Y的距离为b,环长r。

慢指针一次走一步,即slow=slow->next;快指针一次走两步,即fast=fast->next->next。第一相遇在Z点时,slow走过的距离为a+b,fast走过的距离为a+mr+b (m>=1),解释两个问题:一、为什么能遇到?二、为什么第一次相遇时,慢指针slow没有在环内走过n(0<n<m)圈?针对问题一,因为,快指针fast相对慢指针的的速度是1,即,可以看成,慢指针slow静止不动,而快指针fast以速度为1的情况下,在环内前行,所以能遇到。针对问题二,同样的道理,因为fast相对slow的速度是1,假设slow静止,则在fast以速度1完成一圈之前,肯定能遇到slow。

下面分析相遇时,走过的距离,即结点数。slow:a+b;fast:2*(a+b);所以2*(a+b)=a+mr+b(m>=1),故得到a+b=mr,即a=mr-b;所以讲slow放在X点,fast了依旧在Z点,只不过fast的速度降为1,这样,当X到Y的时候,fast也到Y,即得到环的入口点。

1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *detectCycle(ListNode *head) 12     {13         14         ListNode *slow=head;15         ListNode *fast=head;16         //寻找第一个相遇点17         while(fast&&fast->next)18         {19             slow=slow->next;20             fast=fast->next->next;21             if(slow==fast)22                 break;23         }24         //不存在环25         if(fast==NULL||fast->next==NULL)26             return NULL;27         //存在环,slow从头开始,fast从相遇点开始单步走,再次相遇即环的开始点28         slow=head;29         while(slow !=fast)30         {31             slow=slow->next;32             fast=fast->next;33         }34         return slow;35     }36 };

//参考了的博客!!!

 

 相关问题的扩展:参考

1)环的长度是多少?

 方法一:从相遇点开始,让慢指针接着走,并计数,当慢指针slow和快指针再次相遇时,返回计数器的值就行

 方法二:第一次相遇后,让slow,fast继续走,记录到下次相遇时循环了几次。因为当fast第二次到达Z点时,fast走了一圈,slow走了半圈,而当fast第三次到达Z点时,fast走了两圈,slow走了一圈,正好还在Z点相遇。

2)如何将有环的链表变成单链表(即解除环)?

在本题的基础上,从环的入口开始,当指针的next为环的入口结点时,令next指向NULL即可。

转载于:https://www.cnblogs.com/love-yh/p/7019976.html

你可能感兴趣的文章
java web中java和python混合使用
查看>>
创建学员类和教员类
查看>>
Cookie和Session的作用和工作原理
查看>>
字符串操作
查看>>
Visual Studio中改变environment 的布局和显示风格
查看>>
2016-XCTF Final-Richman
查看>>
文件下载
查看>>
extjs grid renderer用法
查看>>
vue 如何在循环中绑定v-model
查看>>
shell脚本
查看>>
[代码笔记]JS保持函数单一职责,灵活组合
查看>>
cmd 重定向
查看>>
【IOS开发】如何画1像素的线
查看>>
【计算机视觉】双目测距(五)--匹配算法对比
查看>>
KMP模板
查看>>
luogu 1314 聪明的质检员
查看>>
[转载]求职者防骗必读!楼主亲身经历告诉你岗前培训多么不靠谱而且违法!
查看>>
Hibernate内存溢出分析一例
查看>>
基于Axis1.4的webservice接口开发(接口调用)
查看>>
Hive内置函数详解
查看>>