blob: d6f9cb4cbe3c0ae6295915e0c749483c6840a049 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
// 142. Linked List Cycle II
#include <stdio.h>
#include <stdlib.h>
/*
* given 'head' of linked list, return node where the cycle begins. if there is
* no cycle return null. there is a cycle in linked list of there is some node
* in the list that can be reached again by continuously following the 'next'
* pointer. internally, 'pos' is used to denote the index of the node that
* tail's 'next' pointer is connected to. it is -1 if there is no cycle. note
* 'pos' is not passed as parameter.
*/
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode *detectCycle(struct ListNode *head) {
struct ListNode *slow = head, *fast = head;
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
break;
}
if (!(fast && fast->next))
return NULL;
while (head != slow) {
head = head->next;
slow = slow->next;
}
return head;
}
|