LeetCode: Linked List Cycle
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了LeetCode: Linked List Cycle，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3716字，纯文字阅读大概需要6分钟。
内容图文
LeetCode: Linked List Cycle
Given a linked list, determine if it has a cycle in it.
Follow up:
Can you solve it without using extra space?
地址：https://oj.leetcode.com/problems/linked-list-cycle/
算法：将链表的指针倒过来，如果最后循环终点是原来链表的头节点，说明链表有环，如果循环的终点不是链表的头节点，那么说明链表没有环（只有一个节点的链表要单独判断）。例如，有如下链表：1->2->3->4->5->6->4(有环的链表，从最后一个节点6又指回第4个节点)，将链表的指针倒过来后变成：1->2->3->4<-5<-6<-4(表示第4个节点指像第6个节点)，注意前面四个节点的顺序被倒置了两次，因为如果有环的话循环会回到第4个节点，然后从第4个节点又循环到头节点。这里不足的地方是改变了原来的链表，但如果你再次从头节点开始将链表指针在倒置一次则又会回到原来的链表。代码：
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
bool hasCycle(ListNode *head) {
12if (!head)
13returnfalse;
14if(!head->next)
15returnfalse;
16if(head->next == head)
17returntrue;
18 ListNode *p = head;
19 ListNode *pre = NULL;
20 ListNode *old_head = head;
21 head = NULL;
22while(p){
23 pre = p;
24 p = p->next;
25 pre->next = head;
26 head = pre;
27 }
28if(pre == old_head)
29returntrue;
30returnfalse;
31 }
32 };
上述的方法可以利用常数空间来判断一个链表是否存在环，但如果题目要求找到这个环的起点，那么上述方法应该无法利用常数空间来解决了。以下的方法是参考网上的答案，这种方法不仅可以判断一个链表是否存在环，而且可以找到该环的起点节点。具体的思想：初始化两个指针，一个为slow，一个为fast，二者的初始值都为表头节点，然后每次让slow往后走一个节点，fast往后走两个节点。若没有环，则二者肯定不会相遇；若存在环，则二者肯定会在环中某个节点相遇。证明如下：
假设从表头节点到环开始的节点长度为a，环的总长度为k，设slow在所在节点距离环开始处的距离为b，由于slow每次只走一步，则b的取值范围为[0,k-1]，
另外设c=k-b。举个例子，假如链表为1->2->3->4->5->6->4，则a=3，k=4，若slow位于第4个节点，则b=0，c=4；若slow位于第6个节点，则b=3，c=1。现在假设slow走的总步数为a+b+tk，其中t表示slow在环中循环了t次，那么由于fast走的步数是slow的两倍，故fast走的总步数为2(a+b+tk)，所以fast将停留的节点距离环开始的节点距离为a+2b，现在假如我们能够找到一个自然数n，使得a+b=nk，那么我们就可以保证fast停留的位置与slow的位置一样。很显然，由于b可以取0到k-1中的任意值，故无论a为何值，我们总能找到一个满足a+b=nk的b值，即slow指针和fast指针最终必定会相遇。具体代码如下：
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
bool hasCycle(ListNode *head) {
12if (!head || !head->next){
13returnfalse;
14 }
15if (head->next == head){
16returntrue;
17 }
18 ListNode *fast = head;
19 ListNode *slow = head;
20while(fast && slow){
21 slow = slow->next;
22 fast = fast->next;
23if(fast) fast = fast->next;
24if(fast == slow){
25break;
26 }
27 }
28if(fast)
29returntrue;
30else31returnfalse;
32 }
33 };
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Follow up:
Can you solve it without using extra space?
地址：https://oj.leetcode.com/problems/linked-list-cycle-ii/
算法：第二题与第一题不同的是，不仅要判断链表是否存在环，而且如果存在环的话还要找到环开始的起点。这里所用的方法也是接上面的方法，假如存在环的话，那么利用上面的方法，slow跟fast能够在环当中的某个节点相遇，并且跳出循环。此时，固定住fast不变，将slow设置为表头节点，然后让二者同步的往后走，则在经过a步后二者必定相遇，且相遇的节点必为环的开始节点。证明如下：
假设经过第一题的方法后，slow和fast在距离环开始节点为b时相遇，另在假设fast指针经过a步后绕环走了t圈，并且最终停留在距离环开始节点为d时停下来，现在我们要证明的是d=0。根据题意可知
d=a-tk-c=a-tk-(k-b)=a+b-(t+1)k，根据上面一题的证明可知a+b能够被k整除，故d一定等于零，也就是说fast在经过a步后一定停留在环开始的节点。第二题代码：
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) {
12if (!head || !head->next){
13return NULL;
14 }
15if (head->next == head){
16return head;
17 }
18 ListNode *fast = head;
19 ListNode *slow = head;
20while(fast && slow){
21 slow = slow->next;
22 fast = fast->next;
23if(fast) fast = fast->next;
24if(fast == slow){
25break;
26 }
27 }
28if(fast != slow){
29return NULL;
30 }
31 slow = head;
32while(fast != slow){
33 fast = fast->next;
34 slow = slow->next;
35 }
36return fast;
37 }
38 };
原文：http://www.cnblogs.com/boostable/p/leetcode_linked_list_cycle.html
内容总结
以上是互联网集市为您收集整理的LeetCode: Linked List Cycle全部内容，希望文章能够帮你解决LeetCode: Linked List Cycle所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。