👀 문제
https://leetcode.com/problems/linked-list-cycle-ii/submissions/
👊 도전
1. 설계
- ListNode의 사이클 시작점부터를 반환한다.
- 이때 공간 복잡도 O(1)을 만족하는 코드를 짠다.
2. 구현
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
/**
*
* @author HEESOO
*
*/
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
ListNode fast=head, slow=head;
while(fast!=null && fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast==slow){ // 사이클이 있다면
ListNode slow2=head;
while(slow!=slow2){
slow=slow.next;
slow2=slow2.next;
}
return slow;
}
}
return null;
}
}
3. 결과
🤟 성공 🤟
문제 제한조건을 못보고 HashSet을 이용하여 문제를 풀었었다.
4. 설명
- 리스트에 사이클이 있는지 확인한다
- fast는 리스트를 두 칸씩 뛰는 포인터, slow는 한 칸씩 뛰는 포인터이다.
- fast가 리스트의 마지막까지 간다면 사이클이 없다는 뜻이다.
- fast==slow가 만나는 지점이 사이클 구간 중 한 군데이다.
- 사이클의 시작점을 찾는다
- 리스트 시작부터 사이클 시작점까지의 구간을 a, 사이클 내 fast와 slow가 만난 곳을 b(사이클 시작점~만난 곳), b를 제외한 사이클 나머지 구간을 c라고 하자.
- fast와 slow가 만나기 위해 fast는 a+b+c+b=a+2b+c를 이동한다.
- slow는 a+b
- fast==slow이므로 a+2b+c=a+b (1)
- fast는 slow보다 2배 빠르므로 a+b=2(a+b) (2)
- 식 (1), (2)를 통해 a=c라는 결론을 얻을 수 있다.
- 따라서 리스트 시작점(head)에서부터 움직이는 포인터 slow2와 fast와 slow가 만난 점에서부터 사이클 시작점으로 가는 slow가 만나는 점이 정답이다.