32. Linked List Cycle II

문제

연결 리스트에 사이클이 있으면 사이클이 시작하는 노드를 반환하라.

사이클이 없다면 null을 반환하라.

 

해결 방식

https://leetcode.com/explore/learn/card/linked-list/214/two-pointer-technique/1214/discuss/44902/Sharing-my-Python-solution

Floyd의 순환 찾기 알고리즘 이용.

slow, fast 포인터로 사이클이 존재하는지 아닌지 확인한다.

사이클이 존재한다면 slow, fast 포인터가 만나는 지점에서 while문을 탈출한다.

 

이 시점에서 head, slow를 한 칸씩 앞으로 보내다 보면 

head와 slow는 사이클이 시작하는 노드에서 만나게 된다.

def detectCycle(self, head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

        if slow == fast:
            break

    else:
        return None

    while head != slow:
        slow = slow.next
        head = head.next

    return head