[LeetCode | Python] 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.

 

linked list에 사이클이 있는지 감지하는 문제!

 

풀이1: Hash Set

# 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:
        seen = set()
        cur = head
        while cur:
            if cur in seen:
                return True
            seen.add(cur)
            cur = cur.next
        return False

방문한 노드를 set에 저장하고, 동일한 노드를 하면 사이클이 존재한다고 판단한다.

구현이 간단하지만, 추가 메모리 공간이 필요하다. 

시간 복잡도는 O(n), 공간 복잡도는 O(n)이다.

 

 

풀이2: Fast And Slow Pointers

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

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

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

두 개의 포인터를 사용하여, 

하나는 한 칸(slow), 다른 하나는 두 칸(fast)씩 이동한다.

두 포인터가 만나면 사이클이 존재한다고 판단한다.

메모리를 적게 사용하는 효율적인 방법이다!

시간 복잡도는 O(n), 공간 복잡도는 O(1)이다.