142. Linked List Cycle II - medium
문제
Given a linked list, return the node where the cycle begins. If there is no cycle, return null.
To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.
Note: Do not modify the linked list.
제한사항
- Can you solve it without using extra space?
입출력 예
1
2
3
Input: head = [3,2,0,-4], pos = 1
Output: tail connects to node index 1
Explanation: There is a cycle in the linked list, where tail connects to the second node.
1
2
3
Input: head = [1,2], pos = 0
Output: tail connects to node index 0
Explanation: There is a cycle in the linked list, where tail connects to the first node.
1
2
3
Input: head = [1], pos = -1
Output: no cycle
Explanation: There is no cycle in the linked list.
풀이
- Linked List, two pointer
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
35
36
37
38
39
40
41
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if (head == NULL || head->next == NULL)
return NULL;
ListNode *slower = head;
ListNode *faster = head;
ListNode *temper = head;
// 항상 faster가 빠르므로, fastet->next, fastet->next->next가 nullptr일때 nullptr을 리턴
while (faster->next && faster->next->next){
// slower는 한 노드씩 증가
// faster는 두 노드씩 증가
slower = slower->next;
faster = faster->next->next;
// slower와 faster가 같다면 기본적으로 cycle이 형성된다고 볼수 있음
if(slower == faster){
// cycle이 형성된 상태에서 head부터 한 노드씩 증가하는 temper와
// 현재 slower에서 한 노드씩 증가할때,
// temper와 slower가 같아지는 노드가 cycle 지점
while(slower != temper){
slower = slower->next;
temper = temper->next;
}
return slower;
}
};
return nullptr;
}
};