首页 > 代码库 > LeetCode:Linked List Cycle II
LeetCode:Linked List Cycle II
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?
思路：第一次按照Linked List Cycle的解法去做，果断超时。最后参考了网上的思路如下：
（1）定义slow和fast指针，都指向head结点，然后slow指针每次向后走1个结点，fast指针每次向后走2个结点。
（2）如果fast指针为空，则说明不存在环；如果fast指针和slow指针相等，则说明存在环。
（3）存在环时将slow指针指向head结点，然后slow指针和fast指针每次都向后走一个结点。
（4）如果slow指针和fast指针相等，该处结点就是环的开始结点，返回slow指针。
本文参考了：http://blog.csdn.net/cs_guoxiaozhu/article/details/14209743
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 if(head==NULL||head->next==NULL)13 return NULL;14 ListNode *slow=head,*fast=head;15 while(fast!=NULL)16 {17 slow=slow->next;18 fast=fast->next;19 if(fast!=NULL)20 fast=fast->next;21 if(slow==fast)22 {23 slow=head;24 while(slow!=fast)25 {26 slow=slow->next;27 fast=fast->next;28 }29 return slow;30 }31 }32 return NULL;33 }34 };
LeetCode:Linked List Cycle II
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。