[LeetCode 142.] Linked List Cycle II (Java)

문제

https://leetcode.com/problems/linked-list-cycle-ii/

linked list에 head가 주어진다. 이때 사이클이 시작하는 노드를 return 한다. 없는 경우 null을 return 한다.

풀이

1. 사이클인지 판별한다.

2. 사이클인 경우 사이클의 진입부분을 찾는다.

"토끼와 거북이 알고리즘" 을 사용한다.

1. 거북이를 시작지점으로 옮긴다.

2. 토끼와 거북이가 만날 때까지 한칸씩 이동한다.

3. 둘이 만나는 지점이 사이클의 시작지점이다.

 

D : 시작점(head)에서 사이클 시작점까지의 거리
M : 사이클 시작점에서 둘이 만난 지점까지의 거리
R : 둘이 만난 지점부터 다시 사이클 시작점까지의 거리

 

거북이 = D + M
토끼 = 2(D + M) = 2D+2M

 

토끼는 거북이의 2배씩 움직이므로, 위의 수식은 쉽게 구할 수 있다.

이때 토끼가 이동한 경로는 시작점 -> 사이클 시작점 -> 둘이 만난 곳 -> 사이클 시작점 -> 둘이 만난 곳이 된다.

이제 토끼가 이동한 경로를 D,M,R을 사용하여 표시를 해보면 다음과 같다.

 

토끼 = D + M + R + M = D + R + 2M

 

이제 토끼가 이동한 거리를 표현한 수식이 2개가 되었다. 이 두 개를 가지고 R과 D의 관계를 계산할 수 있다.

2D + 2M = D+R+2M 
-> D = R

D = R, 즉, "시작점부터 사이클 시작점 까지의 거리"는 "둘이 만난 곳 부터 다시 사이클 시작점까지 가는 거리"와 같다.

이 알고리즘이 옳다는 것을 증명했으므로, 이를 사용해 구현하게 되면 어렵지 않게 문제를 해결할 수 있다.

Java Code

/**
 * 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) {
        if(head==null || head.next==null) return null;
        
        ListNode slow = head;
        ListNode fast = head;
        while(fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
            if(slow==fast){
               while(head!=slow){
                   head=head.next;
                   slow=slow.next;
               }
               return slow;
            }
        }
        return null;
    }
}