[ leetcode 문제풀이 ] Linked List Cycle

Linked List Cycle - LeetCode

Linked List Cycle - LeetCode

(Linked List Cycle 문제는 위 링크에서 풀어보실 수 있습니다.)

 

 

 

< Linked List Cycle 문제 설명 >

 

Linked List Cycle 문제는 다음과 같다. 

Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.

 

linked list의 헤드가 주어졌을 때 linked list에 cycle이 있는지 확인하여라.

linked list의 next 포인터를 계속 따라감으로써 다시 도달할 수 있는 node가 있는 경우 linked list에 cycle이 있는 것이다. 내부적으로 pos는 tail의 next 포인터가 가리키는 node의 index를 나타내는 데 사용된다. pos는 매개 변수로 전달되지 않음에 유의하라.

linked list에 cycle이 있는 경우 true를 리턴하고, 그렇지 않은 경우 false를 리턴하여라.

 

다음 세 가지 출력 예시가 주어졌다.

 

 

주어진 제한 조건은 다음과 같다:

list의 노드 수는 [0, 10^4] 범위 내에 있다.

-10^5 ≤ Node.val ≤ 10^5

pos 는 -1이거나 linked list의 유효한 index를 가리킨다.

 

Follow up question: O(1) (i.e. constant) memory 만을 사용해 문제를 풀 수 있는가?

 

 

< Linked List Cycle 문제 접근 >

 

cycle이 있는지를 확인하기 위해 사용한 방법은 이미 탐색한 node는 일관되게 하나의 노드(=EndNode)를 가리키도록 바꿔두는 것이다. 우선 작성한 코드는 다음과 같다. (Cpp 사용)

 

bool hasCycle(ListNode *head) {
    if(head == nullptr) return false;
    if(head->next == nullptr) return false;
        
    ListNode EndNode(0), *pointNext = head;
    while(head->next != &EndNode){
        pointNext = head->next;
        head->next = &EndNode;
        head = pointNext;
        if(head->next == NULL) return false;
    }
    return true;
} // runtime : 8 ms (faster than 95.72 %), memory usage : 8 MB (faster than 81.49 %)

 

코드를 보면 head에서부터 한 번 방문한 node는 EndNode를 가리키도록 설정하였다. 이때, pointNext는 head의 다음 노드를 가리킨다.

 

while loop의 종료 조건은 head→next가 EndNode인 경우이다. 한 번 방문한 node의 경우 next를 EndNode가 되도록 설정하였기 때문에 while loop 진행과정에서 head→next가 EndNode인 경우, 이미 방문한 노드를 한 번 더 방문했다는 뜻이므로 cycle이 있다는 것이다(return true) while문이 실행되는 중에 head→next가 NULL인 경우는 list의 마지막에 도달했다는 것이므로 cycle은 존재하지 않는다. (return false)

 

time complexity : O(n), space complexity : O(1)