Linked List Cycle

Linked List (singly) 도, Tree도 모두 DAG인 그래프의 일종이라 할 수 있다. 그래프의 사이클을 찾는 방법은 크게 방문된 노드를 기록해 두었다가 (O(n) space), 방문하려는 노드가 이미 방문한 적이 있다면 cycle 이 있다고 보고하는 방법과, Floyd가 제시한 two pointer를 사용하는 방법이 있다 (O(1) space). 이전에 전자에 대해 다루었으므로 오늘은 후자를 다뤄본다. 아무래도 공간을 사용한 전자가 더 속도가 빠르기는 하다.

사이클 여부

토끼는 2걸음씩, 거북이는 1걸음씩 걷는다. 사이클이 존재한다면 둘이 만날 것이고 그렇지 않다면 토끼가 먼저 종점에 도달할 것이다.

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

# Approach 2: Floyd's Cycle Finding Algorithm O(1) space
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None: return False
        slow, fast = head, head.next
        while slow != fast:
            if fast is None or fast.next is None:
                return False
            slow, fast = slow.next, fast.next.next
        return True

여기서 재미있는 부분은 slow, fast에서 1걸음 차이를 두고 시작했다는 것이다. 이렇게 하면 예외 케이스를 처리하기 용이한 것 같다. 결국 우리가 slow와 fast 포인터를 활용하려고 하기 때문에 아래 케이스가 발생하면 termination을 시켜줘야 한다.

# Slow: S, Fast: F

< case 1 >
None    # if node is None: return False

< case 2 >
S       F
node -> None     # if fast is None: return False

< case 3 >
S       F
node -> node -> None    # if fast.next is None: return False

속도로 볼 때 더 빠른 방식은 그저 아래처럼 slow, fast를 애초에 head로 놓는 방법이지만 위 방식이 많은 참고서적에서 언급되는 것으로 봐서 스탠다드인 것 같다.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            
            if slow == fast:
                return True
        
        return False

사이클 시작점 찾기

우선 두 포인터가 만나는 시점에 사이클 여부는 판명이 됐고, 그 다음 문제는 어디서 사이클이 시작되는지이다. 약간의 수학적 사고가 필요하다. slow는 k 걸음을, fast는 2k 걸음을 걸었고, 사이클의 길이는 미지수 c, 시작점까지의 길이를 s라고 하자. 그러면 fast - slow = 2k - k = k = (s + nc) - (s + mc) = (n-m)c 이며 (n, m: slow와 fast가 사이클을 돈 횟수), k % c == 0 이다. 그러므로 s를 구하기 위해서는 slow를 다시 시작점으로 옮겨, slow와 fast가 한 걸음씩 걷도록 해서 만나는 점을 찾는다 (참고: https://web.archive.org/web/20160401024212/http://learningarsenal.info:80/index.php/2015/08/24/detecting-start-of-a-loop-in-singly-linked-list/)

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow = fast = head
        while (fast != None and fast.next != None):
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return slow
        return None
    
    def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        fast = self.hasCycle(head)
        if fast != None:
            slow = head
            while slow != fast:
                slow, fast = slow.next, fast.next
            return slow
        else:
            return fast

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

Linked List Cycle II - LeetCode

사이클의 길이

시작점을 구했으므로, 한 포인터는 그곳에 두고, 나머지를 한발씩 움직이며 길이 카운터를 1씩 증가하는 일을 둘이 만날 때 까지 한다.