[Leetcode 아주 상세한 문제풀이] 141. Linked List Cycle – 코드 line 별 설명

Leetcode 문제

이번에 풀어볼 문제는 리트코드 141번 문제 Linked List Cycle 이다.

우선 문제를 살펴보자.

 

리트코드 141번 문제 Linked List Cycle 링크

Linked List Cycle - LeetCode

Linked List Cycle - LeetCode

 

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.

Example 1:
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
 
Constraints:
The number of the nodes in the list is in the range [0, 104].
-105 <= Node.val <= 105
pos is -1 or a valid index in the linked-list.

 

 

문제 설명

문제를 간략히 살펴보자. Linked list로 표현되는 배열이 인풋으로 주어진다. 이때 주어진 linked list가 cycle (닫힌 고리)을 이루는지 확인하라는 문제다. 이때 pos라는 값이 인풋으로 주어지는데 이는 linked list의 꼬리(trail)가 몇번째 인덱스와 이어졌는지를 나타낸다. 문제 예시 1번에서 보는 것처럼 [3, 2, 0, -4]라는 배열이 주어졌다고 생각해보자. 이때 각 element는 3->2->0->-4 순서대로 linked list로 연결되어 있다. 이때 pos 값은 1로 주어졌기 때문에 -4 노드에서 나오는 꼬리가 1번 인덱스 (=pos)에 해당하는 2 노드에 연결이 되어 있다. 따라서 이 경우 주어진 배열과 pos값을 고려할 때 cycle이 존재한다고 할 수 있다. 문제 이해가 어렵지 않으니 곧바로 문제를 풀어보자.

 

 

문제 접근법

이 문제를 해결하기 위해서는 토끼와 거북이 전략을 쓸 것이다.

우리는 주어진 linked list를 처음부터 탐색을 할 것인데 두 개의 포인터를 만들어 탐색할 것이다.

이때 느린 거북이 포인터는 1간씩 탐색을 하고 빠른 토끼 포인터는 2칸씩 탐색을 할 것이다.

이 과정을 거치다보면 주어진 linked list내 cycle이 존재할 경우 이 두 포인터는 반드시 만나게 된다.

따라서 두 개의 포인터가 만나느냐 안 만나느냐에 따라 cycle의 존재 유무를 확인할 수 있다.

코드로 한 번 살펴보자.

 

 

문제 풀이

Linked list를 표현하기 위한 클래스를 선언해준다. (line 1-4)

이는 파이썬에서 일반적으로 사용되는 표현식이니 익숙해 지도록 하자.

이제 인풋 배열을 입력받기 위한 함수를 정의해 준다. (line 6)

만약 입력받은 배열이 비어있거나 혹은 head 하나만 존재할 경우 false를 리턴해준다. (line 7-8)

우리는 cycle 존재 유무를 확인하고자 하는데 이 경우 cycle 자체가 존재할 수 없기 때문이다.

그리고 앞서 설명한 두 개의 포인터를 만들어준다. 

느린 거북이 포인터 (slow)는 head에 위치시키 빠른 토끼 포인터 (fast)는 head 바로 다음에 위치시킨다. (line 10-11)

이제 slow와 fast 포인터가 서로 만나지 않는 동안 탐색을 계속할 것이다. (line 13)

탐색을 하는 와중 fast 포인터가 가리키는 노드가 없거나 혹은 fast 포인터가 가리키는 노드 다음 노드가 없다면 false를 리턴해주고 종료한다. (line 14-15)

이 경우 fast 포인터가 주어진 전제 linked list를 탐색했는데도 불구하고 그 와중에 slow 포인터가 만나지 못했다는 뜻이기 때문에 cycle이 존재하지 않음을 의미한다.

만약 이 경우가 아니라면 slow 포인터는 오른쪽으로 한 칸, fast 포인터는 오른쪽으로 투 칸씩 움직이면서 탐색을 계속한다. (line 17-18)

While loop는 slow 포인터와 fast 포인터가 만나지 않는 이상 계속 돌게된다.

만약 두 포인터가 만났다면 while loop를 빠져나오게 된다.

두 포인터가 만났다는 뜻은 결국 linked list 내에 cycle이 존재한다는 것이다.

따라서 이 경우 true를 리턴하고 종료하면 된다. (line 20)

 

 

문제 풀이 코드

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next
 
def hasCycle(head):
    if not head or not head.next:
        return False
 
    slow = head
    fast = head.next
 
    while slow != fast:
        if fast is None or fast.next is None:
            return False
 
        slow = slow.next
        fast = fast.next.next
 
    return True
 
# Helper function to create a linked list from a list of values
def createLinkedList(lst):
    if not lst:
        return None
    head = ListNode(lst[0])
    current = head
    for value in lst[1:]:
        current.next = ListNode(value)
        current = current.next
    return head
 
# Helper function to create a cycle in the linked list
def createCycle(head, pos):
    if pos == -1:
        return head
    cycle_start = None
    current = head
    index = 0
    while current.next:
        if index == pos:
            cycle_start = current
        current = current.next
        index += 1
    current.next = cycle_start
    return head
 
# Example 1
lst1 = [3, 2, 0, -4]
head1 = createLinkedList(lst1)
head1 = createCycle(head1, 1)
print("Example 1: ", hasCycle(head1))  # Should return True
 
# Example 2
lst2 = [1, 2]
head2 = createLinkedList(lst2)
head2 = createCycle(head2, 0)
print("Example 2: ", hasCycle(head2))  # Should return True
 
# Example 3
lst3 = [1]
head3 = createLinkedList(lst3)
head3 = createCycle(head3, -1)
print("Example 3: ", hasCycle(head3))  # Should return False
 

 

 

관련 문제

리트코드 19번 Remove Nth node from end of list 문제 풀이 (링크)

리트코드 21번 Merge two sorted lists 문제 풀이 (링크)

리트코드 23번 Merge K sorted lists 문제 풀이 (링크)

리트코드 143번 Reorder list 문제 풀이 (링크)

리트코드 206번 Reverse a linked list 문제 풀이 (링크)

 

141. Linked List Cycle