[LinkedLists: Fast and Slow Pointers] Linked List Cycle II ★★★★★

142. Linked List Cycle II

 

이 문제는 Linked List Cycle Detection 문제 중 하나로,

**Floyd's Cycle Detection Algorithm (Tortoise and Hare)**를 활용하여 해결할 수 있습니다.

아래는 단계별 풀이 방법입니다.

---

1. Floyd’s Cycle Detection Algorithm (토끼와 거북이)

• 두 포인터(Tortoise와 Hare)를 사용하여 Linked List를 순회합니다.
• 속도 차이를 이용해 두 포인터가 같은 노드에 도달하면 사이클이 있음을 확인할 수 있습니다.
• 사이클이 발견되면, 사이클의 시작 노드를 찾는 추가 작업을 수행합니다.

---

2. 단계별 풀이

1단계: 사이클 존재 여부 확인

1. slow 포인터는 한 번에 한 노드씩 이동합니다.
2. fast 포인터는 한 번에 두 노드씩 이동합니다.
3. 두 포인터가 만나면 사이클이 존재합니다.
4. 만약 fast 또는 fast.next가 None에 도달하면 사이클이 없습니다.

2단계: 사이클의 시작 노드 찾기

1. 사이클이 있음을 확인한 후, slow 포인터를 head로 되돌립니다.
2. slow와 fast를 각각 한 칸씩 이동하며 다시 만나는 지점을 찾습니다.
3. 두 포인터가 만나는 지점이 사이클의 시작 노드입니다.

✅ 수학적 증명

• Let:
  • a: head → cycle 시작까지 거리
  • b: cycle 시작 → 만나는 지점까지 거리
  • c: cycle 전체 길이
• slow = a + b
• fast = a + b + n*c
• fast는 slow 보다 2배 속도
  → 2(a + b) = a + b + n*c
  → 정리하면 a = n*c - b
• 그래서 head에서 다시 출발한 slow 가 a 만큼 이동하면
  →  fast 는 a + b + n*c  + a
                = a + b + n*c + n*c - b
                = a + 2n*c 이므로
• slow는 a 인 cycle 시작점에서 fast와 만나게 됨

class Solution:
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        # 1단계: fast와 slow 포인터를 모두 head로 초기화
        # slow는 1칸씩, fast는 2칸씩 이동하면서 사이클 탐색
        slow = fast = head

        while fast and fast.next:
            slow = slow.next              # slow는 한 칸 이동
            fast = fast.next.next        # fast는 두 칸 이동

            if slow == fast:             # slow와 fast가 만나면 사이클 존재
                # 2단계: slow를 head로 이동시킴
                # fast는 현재 만난 지점에서 그대로 둠
                # 둘을 다시 1칸씩 이동시키면, 사이클 시작점에서 만나게 됨
                slow = head
                while slow != fast:
                    slow = slow.next     # slow 한 칸 이동
                    fast = fast.next     # fast 한 칸 이동
                return slow              # slow와 fast가 만난 노드가 사이클 시작점

        # fast가 None이거나 fast.next가 None이면 리스트 끝 → 사이클 없음
        return None

 

 

 

# Find the middle of a linked list with two pointers.
# Time: O(n), Space: O(1)
def middleOfList(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow


# Determine if the linked list contains a cycle.
# Time: O(n), Space: O(1)
def hasCycle(head):
    slow, fast = head, head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False


# Determine if the linked list contains a cycle and
# return the beginning of the cycle, otherwise return null.
# Time: O(n), Space: O(1)
def cycleStart(head):
    slow, fast = head, 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 None
    
    slow2 = head
    while slow != slow2:
        slow = slow.next
        slow2 = slow2.next
    return slow