Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
Note: Do not modify the linked list.
Follow up:
Can you solve it without using extra space?
分析
一個(gè)簡(jiǎn)單的方法是依次保存指針嫌吠，然后尋找相同的指針節(jié)點(diǎn)。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *array[100000];
int num=0;
struct ListNode *p=head;
while(p!=NULL)
{
for(int i=0;i<num;i++)
{
if(p==array[i])
return array[i];
}
array[num]=p;
num++;
p=p->next;
}
return NULL;
}
但是耗時(shí)比較多。
另一個(gè)方法是經(jīng)過(guò)推導(dǎo)：
using two pointers, one of them one step at a time. another pointer each take two steps. Suppose the first meet at step k,the length of the Cycle is r. so…2k-k=nr,k=nr
Now, the distance between the start node of list and the start node of cycle is s. the distance between the start of list and the first meeting node is k(the pointer which wake one step at a time waked k steps).the distance between the start node of cycle and the first meeting node is m, so…s=k-m,
s=nr-m=(n-1)r+(r-m),here we takes n = 1…so, using one pointer start from the start node of list, another pointer start from the first meeting node, all of them wake one step at a time, the first time they meeting each other is the start of the cycle.
別人的代碼如下：
ListNode *detectCycle(ListNode *head) {
if (head == NULL || head->next == NULL) return NULL;
ListNode* firstp = head;
ListNode* secondp = head;
bool isCycle = false;
while(firstp != NULL && secondp != NULL) {
firstp = firstp->next;
if (secondp->next == NULL) return NULL;
secondp = secondp->next->next;
if (firstp == secondp) { isCycle = true; break; }
}
if(!isCycle) return NULL;
firstp = head;
while( firstp != secondp) {
firstp = firstp->next;
secondp = secondp->next;
}
return firstp;
}
