Linked List Cycle [leetcode]

문제

코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        num_list = []
        
        curr = head
        while True:
            if curr == None:
                return False
            
            if curr not in num_list:
                num_list.append(curr)
                curr = curr.next
            else:
                return True

문제 풀이 과정 설명

 

나는 지나는 모든 노드를 리스트에 저장한 뒤,

사이클이라면 리스트에 중복되는 노드가 분명 존재할 것임으로 해당 조건을 걸어서 사이클을 판단했다.

(이건 space complexity O(n)이다. 노드 개수만큼 만들어야 하므로)

 

하지만 문제 마지막 follow-up 질문을 보면,

O(1)의 메모리 공간으로 사이클을 판단할 수 있는지 물어봐서 한참을 고민했지만

모르겠어서... 위 로직으로 코드를 짜 정답을 받았다.

(하지만 메모리 사용부분에서 엄청나게 낮은 등수...)

 

그래서 도대체 O(1)로는 어떻게 푸는지 봤더니...(discuss 탭 고수분들 bb)

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        if head is None or head.next is None:
            return False
        slow = head
        fast = head.next
        while fast.next and fast.next.next and slow != fast:
            slow = slow.next
            fast = fast.next.next
        return slow == fast

딱 보자마자 와...아... 같은 소리만 하게 된다. 이건 이름도 있더라...Floyd's Tortoise & Hare Algorithm

 

토끼와 거북이가 같은 노선을 달리는데 토끼는 두칸, 거북이는 한칸씩 전진할때

사이클 일 경우, 두마리 동물은 한번은 마주치게 된다. 그걸 코드로 구현하면 저렇게 된다.

 

메모리를 엄청나게 아낄수있는 방법 하나 알게되서 기분이 좋다.