[Linked List][Medium] 142. Linked List Cycle II

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

 

Q. 주어진 Linked list 의 cycle의 시작점을 찾아 반환하라. 없으면 null을 반환하라.

 

Solution

 잘 알려진 linked list의 순환점을 찾는 문제이다. 

 우선 순환을 찾는 방법은 fast와 slow pointer를 운용하면서 두 포인터가 만나는 지점을 찾는 것이다. 

 이때 두 포인터가 만나는 부분은 head부터 cycle의 순환 시작점까지 거리를 k 라고 한다면

 slow가 cycle 시작점에 위치 시, fast는 loop안에서 k 앞의 위치에 있다. 

 즉 현재 fast의 위치는 loop안에서 k, slow는 0 이라고 생각할 수 있다.

 

head ---- slow --- fast ----

                |                      |

                -------------------- 

 

> fast - slow = k

> slow- fast = loop_size - k

 

 fast는 slow의 두배를 가므로, slow가 1 앞서서 둘 차이가 1일때 1더 지나면 만난다. 

 2라면 2를 더 지나면 만난다.(fast는 4이동, slow는 2이동)

  

  fast ---- slow ---- ?

 

 

 이제 이것을 수식화 해 보자. 

  fast와 slow와의 거리는 slow가 앞서 있다고 하면 거리차는 loop_size - k 이다. 

  fast가 이 두배의 거리를 가면 만난다. 

 즉, fast 는 현재 위치 + 2배의 거리차 => k + 2 x (loop_size - k) 인 것이다. 

 

  fast ---- slow ---Meet

           |                |

       lps-k           lps-k   

 

 수식을 전개하면 결과적으로 -k 만 남는다.

 즉, 만나는 지점에서 k 만큼 더 가면 cycle 시작 점이라는 것이다. 

 그렇다면 k는 어떻게 구하나, 

 만나게 되면 한 노드를 head로 옮기고 하나씩 전진시켜 두 노드가 만나면 그 이동량이 k 가 된다. 

 

 

 

로직을 코드로 옮긴다. 

public ListNode DetectCycle(ListNode head) 
{
    // find meet point.
    ListNode fast = head;
    ListNode slow = head;
    bool hasCycle = false;
    while(fast!=null && fast.next != null) 
    {
        slow = slow.next;
        fast = fast.next.next;
        if(fast == slow)
        {
            hasCycle = true;
            break;
        }
    }
    if(!hasCycle)   return null;

    // find starting point of the cycle.
    ListNode node = head;
    while(node!=null) 
    {
        if(node == slow)
            return node;

        node = node.next;
        slow = slow.next;
    }
    return null;
}

 

 

적절한 결과를 얻었다.