[DSA][Linked List] 03. Linked List Cycle

LeetCode 141

 

03. 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.

 

 

[질문하기]

- 노드 값의 범위가 존재하나요?

- 빈 연결리스트가 주어질 수도 있나요?

 

 

[아이디어]

- 방문 여부를 체크하기 위해 노드의 값을 주어질 수 없는 범위의 값으로 변경한다.

- hashSet을 사용하여 방문 여부를 체크한다. (공간복잡도 O(n))

- 속도가 다른 두 포인터로 노드를 탐색한다.

 

 

[풀이 1] Linked List

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        hasCycle = False
        cur = head
        while cur:
            if cur.val == 1e9:
                return True
            else:
                cur.val = 1e9
            cur = cur.next

        return False

노드의 값이 -10⁵에서 10⁵ 사이로 제한되어 있다는 조건이 명확히 주어졌기 때문에, 방문한 노드의 val 값을 특정한 임시 값(1e9)으로 바꾸는 방식으로 사이클을 탐지할 수 있다. 만약 이후에 1e9 값을 가진 노드를 만나게 되면, 이는 이전에 방문한 노드라는 의미이므로 사이클이 존재한다고 판단할 수 있다.

 

하지만 이 방식은 원래 값이 의미 있는 경우, 임의의 값을 덮어쓰기 때문에 원본 데이터를 손상시키는 문제가 있다. 그리고 싸이클이 처음 생긴 위치를 알아내야 하는 경우에는 단순히 값을 바꾸는 방식으로는 위치 정보를 알 수 없다. 이러한 이유로 일반적으로는 Floyd’s Cycle Detection Algorithm (Tortoise and Hare) 같이 포인터 기반 방식을 사용하는 것이 더 안전하고 확장성이 좋다.

 

 

[풀이 2] Floyd’s Cycle Detection Algorithm

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 fast == slow:
                return True
        return False

이 알고리즘은 일명 "토끼와 거북이 알고리즘"이라 불리는데, 이 알고리즘을 사용하면 사이클이 존재 여부뿐만 아니라 사이클이 시작되는 위치도 알아낼 수 있 다. 한 번에 한 칸을 움직이는 SLOW 포인터와 한 번에 두 칸을 움직이는 FAST 포인터를 사용하면 사이클이 존재할 때 두 포인트는 반드시 만나게 되고, 이를 바탕으로 사이클 시작 위치도 알 수 있다. 이 알고리즘에 대해서는 별도의 포스팅을 작성하였다. 2025.06.28 - [자료구조와 알고리즘] - Floyd’s Cycle Detection Algorithm

 

⏱️ 시간복잡도

노드를 한번 순회하기 때문에 시간 복잡도는 O(n)이다.

🧠 공간복잡도

고정된 변수들만 사용하므로, 공간 복잡도는 O(1)이다.