23.03.09. 풀었던 문제들

Leetcode 142. Linked List Cycle II

 어떤 linked list의 head가 주어졌을 때 cycle이 없으면 NULL, cycle이 있으면 cycle의 시작 vertex를 리턴하는 문제. space를 O(n)으로 쓰면 set같은 걸 써서 중복검사를 통해 쉽게 풀 수 있다. 그러나 O(1)로 풀어야 하는 게 진짜인 문제.

 

 2개의 pointer를 이용해 답을 구할 수 있다. 한 번에 2개 뒤로 이동하는 fast pointer, 한 번에 1개 뒤로 이동하는 slow pointer 이렇게 2개를 둔다.

• 만약 cycle이 없다면 fast는 진행 중 NULL을 만난다. 이 경우 return NULL
• cycle이 있다면 fast는 slow보다 항상 빠르기 때문에 k바퀴를 돈 후 slow pointer와 같은 vertex를 가리키게 됨.
  • 시작 지점 - cycle 시작 지점을 a, cycle 시작 지점 - 만나는 지점을 b, 만나는 지점 - cycle 시작 지점을 c로 두자.
  • 그러면 fast의 속도는 slow보다 2배 더 빠르기 때문에 2(a + b) = a + b + k(c + b)가 성립한다.
    • 좌항은 slow pointer가 간 거리, 우항은 fast pointer가 간 거리. k(c+b)는 cycle을 k바퀴 돈 것이다.
  • k = 1을 넣으면 fast가 1바퀴 돌고 만나는 지점이 된다. 이 때 2a + 2b = a + 2b + c이므로 a = c
  • 즉 slow와 fast가 만났을 때, 거기서 a만큼 더 가면 그곳이 cycle 시작 지점이다.
    • 만났을 때부터 fast를 1칸씩 움직인다. linked list의 시작지점부터 1칸씩 움직인다. 이렇게 움직이면 둘의 움직인 거리가 같게 된다. 이 둘이 만나는 순간, a만큼 더 간 것이며 그곳이 cycle 시작 지점이다.

 

 코드는 아래와 같다.

// Runtime￦ 0 ms Beats 100%
// Memory 7.7 MB Beats 29.86%

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while(1){
            if(fast == NULL || fast->next == NULL) return NULL;
            fast = fast->next->next;
            slow = slow->next;
            // 만났다면 fast를 a만큼 보내야 함
            if(fast == slow){
                while(head != fast){
                    head = head->next;
                    fast = fast->next;
                }
                return fast;
            }
        }
        return NULL;
    }
};

 

시간복잡도

 앞에서부터 순회하며 최대 a + b + c + b번으로 slow와 fast가 같아지는 지점을 찾고 a번 더 가기 때문에 약 2n이다. 따라서 O(n)

 

공간복잡도

 추가 공간은 상수만 사용하기 때문에 O(1)

 

후기

 대체 이런 건 어떻게 생각하는 건지 모르겠다. 증명에 한참 걸렸다...