LeetCode 142(Linked List Cycle II, Python)

1. 문제 링크

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

 

2. 문제 설명

• 연결 리스트(Linked List)에서 순환(사이클)이 발생하는 경우, 순환의 시작 지점 노드를 반환하고, 사이클이 없으면 None 반환

3. 처음 풀이

• 노드를 한 칸씩 전진하며 set에 저장하고, 이미 들어있으면 그 노드를 반환. 끝까지 갈 동안 같은 노드가 나오지 않으면 사이클이 없으므로 return None
• 공간 복잡도 O(n)으로 좋지 않다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        memo = set()

        cur = head
        while cur:
            if cur in memo:
                return cur
            else:
                memo.add(cur)
                cur = cur.next
        return

 

---

• 더 고민해서 나온 좋은 풀이
• head에서 3칸 이동하면 싸이클의 시작 지점이고, 싸이클의 길이가 5인 상황을 생각해보자.

	0 -> 1 -> 2 -> 3(8) -> 4(9)
                   ↗             ↘ 
	             7(12) <- 6(11) <- 5(10)

• slow, fast가 head에서 출발하고 slow는 한 칸씩, fast는 두 칸씩 이동한다고 해보자. 사이클이 없다면 fast는 끝까지 가버리고, 사이클이 있다면 slow와 fast는 언젠가 만난다. (상대 속도가 한 칸이므로 언젠가 무조건 만난다.)
• 그러면 만났을 때를 생각해보면 slow가 x칸 갔을 때 fast는 2x칸 갔을 것이다. 위 상황에서는 5(10)에서 만난다.
• 여기서 5는 사이클의 길이 5와 같다… 우연일까?
• 그렇지 않다. 몇 가지 상황을 더 관찰해보아도 그렇다.
• 물론 아닌 경우도 있다.(위의 상황과 반대로 5칸 이동 시 사이클 시작, 사이클 길이가 3인 경우 slow가 3칸 이동 시 아직 만나지 않는다. 하지만 3+3칸 가면 만난다.)
• 그 이유를 생각해보면 slow가 x칸, fast가 2x칸 이동했을 때 이동 거리의 차는 x이고 만나려면 주기의 길이 n으로 나누었을 때 그 값이 같아야 하므로 x를 n으로 나눈 나머지는 0이다. 따라서 x가 n, 2n, 3n, … 일 때 만나게 된다.(n, 2n, 3n, … 중 사이클 시작 지점까지 거리 보다 긴 값에서 만남)
• 일반화해서 slow가 kn, fast가 2kn 칸 이동하여 만났다고 하자.
• 그리고 위 상황에서 5(10)에서 만났을 때 또 재미있는 사실은, 사이클의 시작인 3(8)까지 3칸을 더 가면 되는데 이 3칸이 head에서 사이클 시작 지점까지의 길이도 3이라는 것이다.
• 그러니까 두 포인터가 5(10)에서 만난 순간 출발 지점 0에서 새로운 포인터를 출발시키면 새로운 포인터가 slow 포인터가 만나는 지점이 바로 사이클의 시작 지점인 3(8)이라는 것이다.
• 수학적으로 생각해보자. slow가 kn, fast가 2kn칸 이동해서 처음 만났다고 하고 head에서 사이클 시작 지점까지 p칸이라고 하자. 이때 slow가 p칸 더 이동하면 kn+p 만큼 이동하였다. 이를 다르게 생각하면 head로 부터 p칸 이동후 kn을 움직였으니 사이클을 k바퀴 돌고 제자리에 온다. 즉, 사이클이 시작되는 지점에 있게 된다. 말로해서 복잡해보이지만 수식으로 쓰면 간단하다.
• 요약하자면 slow, fast를 출발시키고 만나면, head에서 새로운 포인터를 출발시켜 slow와 만나는 지점, 그곳이 사이클의 시작 지점이다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                break
        
        if not fast or not fast.next:
            return
        
        slow = head
        
        while slow != fast:
            slow = slow.next
            fast = fast.next
        
        return slow

4. 다른 풀이

• 찾아본 다른 사람들의 풀이 모두 2번째 풀이와 같은 논리였음. 

5. 배운 점

• Linked List에서 slow, fast 기법은 정말 유용하다.
• 간단한 상황을 많이 나열해보고 관찰하면서 규칙을 찾을 수 있었다. 수학문제와 마찬가지로 코드 역시 화면을 바라보며 생각하기보다 손으로 그림 그려보며 생각하는게 좋다. 간단한 상황으로 바꾸어 관찰하는게 도움이 된다.
• 관찰한 결과를 논리적으로 확신을 가질 때 수학적인 사고가 핵심적이었다. 코딩과 수학은 불가분의 관계이다.