[LeetCode 해석 및 풀이] 141. Linked List Cycle

LeetCode 문제 해석 및 풀이 방법

 

문제 141. 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.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

 

한글

연결 리스트의 머리인 head가 주어지면 해당 견결 리스트에 순환이 있는지 결정하십시오.

 

몇몇 노드가 next 포인터를 계속 따라갔을 때 다시 방문할 수 있다면 연결 시트에 순환이 있는 것입니다. 내부적으로, pos는 꼬리의 next 포인터가 연결되있는 노드의 인덱스를 나타냅니다. pos는 파라미터로 주어지지 않는 것을 주의하세요.

 

만약 연결 리스트에 순환이 있다면 true를 반환하세요. 아니면 false를 반환하세요.

 

추가 : 당신은 O(1) 메모리(즉, 일정한 메모리)로 문제를 풀 수 있습니까?

 

제한조건

• The number of the nodes in the list is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• pos is -1 or a valid index in the linked-list.

 

입출력 예

첫 번째 경우

두번째 경우

세 번째 경우

 

입력	출력
head = [3,2,0,-4], pos = 1	true
head = [1,2], pos = 0	ture
head = [1], pos = -1	false

 

 

해답 및 해설

파이썬 (Python)

해쉬 맵을 이용한 풀이

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        node_set = set()

        while head:
            if head in node_set:
                return True

            node_set.add(head)
            head = head.next

        return False

 

단순하게 지나왔던 노드들을 집합에 저장한다. 만약 새로 보는 노드가 집합에 저장되어있으면 순환이 있어 이미 지나왔던 노드를 재방문 한 것이므로 True를 반환한다. 모든 노드를 돌아봤음에도 그렇지 않다면 False를 반환한다. 하지만 해당 풀이는 고정된 메모리를 이용한 풀이가 아니다

 

투 포인터를 이용한 풀이 (floyd's 순환 찾기 알고리즘)

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        # slow.next | fast.next.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

한번에 한 노드씩 넘어가는 느린 포인터와 한번에 두 노드씩 넘어가는 빠른 포인터를 둔다. 만약 두 포인터가 같아지는 지점이 온다면 순환이 있는 것이므로 True를 반환한다. 그렇지 않고 next에 다음 노드가 없는 상황이 먼저오면 False를 반환한다.

 

해당 풀이는 왜 되는가? 두 포인터가 루프에 진입했을 때를 생각해보자. 이 때 느린 포인터가 앞에 있고, 빠른 포인터가 뒤에 있다고 관점을 바꿔보면 반복할 때마다 간격이 하나씩 줄어든다고 볼 수 있다. 그렇다면 언젠가는 같아지는 지점이 오게 될 것이다. 마치 원형 경기장에서 느린 거북이와 빠른 토끼가 같이 뛴다 했을 때, 빠른 토끼가 언젠가는 거북이를 따라잡게 되는 것과 같다. 

 

해당 알고리즘을 floyd's cycle-finding algorithm이라고 부르는 듯 하다.

 

class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
        fast = head.next.next if head and head.next else None
        slow = head

        while fast and fast is not slow:
            fast = fast.next
            if fast:
                fast = fast.next
            slow = slow.next

        return bool(fast)

투 포인터를 이용한 다른 풀이. 마지막엔 만약 순환이 없다면 fast값이 None이 되어 bool로 바꾸면 False가 되고 아니면 True가 됨을 이용하였다.