leetcode : Linked List Cycle II

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

Linked List Cycle II - LeetCode

 

진짜 너무 어렵다

이게 뭐냐 진짜 이게 무슨 medium이야 ㅠㅠㅠ

discussion을 보고도 이해를 못해서 거진 1시간을 고민했다.

 

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ 진짜 어렵다 이거

일단 이 Linked List Cycle I을 안풀어봤다면 먼저 풀어보고 와야한다. (https://leetcode.com/problems/linked-list-cycle/)

 

Linked List Cycle I을 풀어봤다면 two pointers를 통해 cycle감지가 가능함을 이해했을 것이다.

하나는 slow 하나는 fast로 두고 slow는 한 번에 한 칸씩, fast는 한 번에 두 칸씩 움직이다 보면 cycle이 있는 graph에서는 slow와 fast가 만나는 지점이 생긴다. 절대 fast가 slow를 건너뛸 수 없다.

 

cycle이 없는 경우는 Linked List Cycle I에서 한 거처럼 그냥 fast가 언젠가 null에 도달하는지 아닌지만 확인하면 된다. 그리 어렵지 않음. 문제는 cycle 시작점을 어떻게 찾느냐인데

 

head에서 cycle 시작점까지의 거리를 x

cycle 시작점에서 slow와 fast가 만난 지점까지의 거리를 y라고 하자.

slow는 x+y만큼 움직였다. (리트코드 discussion을 보면 slow포인터도 cycle을 몇 바퀴 돌 수 있지 않냐고 하는 사람들 있는데 cycle내에서 slow는 절대 한 바퀴 이상 못돈다. slow가 cycle에 진입한 순간부터 fast가 slow바로 앞에 있다고 해도 반바퀴만 돌면 그새 fast는 한바퀴를 다 돌고오기때문에 따라잡힌다.)

fast는 얼마나 움직였을까? slow의 2배의 속도로 움직이므로 slow가 움직인 거리에 2배해주면 된다. 2(x+y). 근데 cycle의 특성을 이용해서 다른 방법으로 표현할 수도 있다. 어쨌든 둘이 만난지점 (x+y)에서 fast는 cycle을 1바퀴 이상 돌고 왔을 것이다. cycle의 길이를 R이라고 하고 fast가 돈 바퀴 수를 N이라고 할 때 fast가 움직인 거리는 x + y + N*R로 표현할 수도 있다. x + y지점에서 몇바퀴를 돌든 제자리니까.

그니까 fast가 움직인 거리는 2(x+y)이기도 하고 x + y + N*R이기도 한것이다. 2(x+y) = x + y + N*R

식을 정리하면 x + y = N*R이 된다.

이 식을 해석하기만 하면 답을 구할 수 있다.

 

결론부터 말하면 둘이 만난 지점에서 slow를 x만큼만 움직이면 시작점으로 되돌아 온다. x만큼 움직이기 위해서 head에 새로운 포인터를 하나 두고 둘이 만날 때까지 동시에 한칸씩 이동시킨다. 둘이 만나면 거기가 cycle의 시작점이다. (보다 자세한 설명은 코드 밑에..)

 

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        
        while True: # 여기까지는 Linked List Cycle I이랑 똑같음
            if not fast or not fast.next or not fast.next.next:
                return None
            
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                break
                
        answer = head # head에 새 포인터를 하나 두고
        while answer != slow: # 둘이 만날때까지 한칸씩 이동시키면 됨!
            answer = answer.next
            slow = slow.next
            
        return answer

 

 

왜 이게 가능하냐고? 잘생각해보자..

 

slow와 fast포인터가 만난지점에 집중해보자. 여기서 R만큼 이동하면 어디로 가있을까? 제자리다!! R은 사이클의 길이이기 때문에 R의 배수만큼 이동한다면 얼마나 이동하든 제자리일거다. 즉 R만큼 이동해도 제자리고, 2R만큼 이동해도 제자리고, 9999R만큼 이동해도 제자리다. 일반화 하면 N * R (N은 몇바퀴 돌았는지를 의미)만큼 이동하면 제자리라는 것이다.

x + y = N * R이라는 식에서 우리가 쨌든 구하고 싶은건 x다. x의 길이를 알면 head포인터에서 x만큼 움직여서 우리가 원하는 노드를 찾을 수 있으니까. x를 기준으로 식을 정리해보자.

x = N * R - y

자 그러면 slow와 fast포인터가 만난 지점에서 x만큼 이동하면 어디에 가있을까?

x만큼 간다는건 N*R - y만큼 간다는거고.. N*R만큼 가는건 무조건 제자리니까.. -y만큼의 위치에 가있을것이다..!! slow와 fast포인터가 만난지점이 (x+y)니까 여기서 -y만큼하면..? x!!!!!! cycle의 시작점으로 온다!!!!!!

 

이건 내 머리로 풀 수 있는 문제가 아니었다! :D