2.8 루프발견

문제 

순환 연결리스트(Circular linked list ) 가 주어졌을때, 순환되는 부분의 첫째 노드를 반환하는 알고리즘을 작성하라.

순환 연결리스트란 노드의 next포인터가 앞선 노드들 가운데 어느 하나를 가리키도록 설정되어 있는, 엄밀히 말해서는 변질된 방식의 연결리스트를 의미한다.

 

해결법

해법에 있는 해결법은 Runner 기법을 이용해 해결하는데 독특해서 그대로 가져와봤습니다.

 

1. 연결리스트에 루프가 있는지 검사

FastRunner와 SlowRunner가 각각 2칸씩 1칸씩 이동한다면 루프가 있다면 언젠가 충돌한다.

 

2. 언제충돌하지?

루프가 아닌 부분의 크기가 K라고 했을때, SlowRunner가 루프에 진입하기 시작하는 순간은 K번 움직인 순간이고 그순간에 FastRunner는 두배를 움직이므로 LoopSize-K만큼 떨어져 있는 위치에 도달해있을 것이다.

그러면 SlowRunner와 FastRunners는 현재 LoopSize -K 만큼 떨어져있는 것이다.

FastRunner가 2칸 움직일때 SlowRunner가 1칸 움직인다는것은 둘은 한번 이동에 1만큼 멀어진다는것지만 루프안에서는1만큼 가까워진다는 것을 의미할 수 있다. 그러면 즉, SlowRunner가 진입한 후 LoopSize-K 이후에 두 포인터가 충돌한다는 것을 의미함

 

3. 루프시작점은 어디인가?

두 포인터가 충돌한 지점은 루프의 시작점으로부터 LoopSize-K만큼 떨어져 있는 곳이다. 

그말은 즉 충돌점에서 K만큼 이동하면 Loop의 시작점에 도달한다는 뜻이고 , list의 시작점에서 Loop의 시작점까지의 거리가 K이기 때문에 

하나의 포인터를 list의 시작점에, 하나를 충돌한 지점에 두고 같은속도로 움직였을때 만나는 점이 loop의 시작점이 된다.

 

def Solution(head):
    slow = head
    fast = head
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    if fast is None or fast.next is None:
        return None

    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return fast