LeetCode [141]: Linked List Cycle

📌 LeetCode [141]: Linked List Cycle

🔗 문제 링크

---

문제 설명 📄

주어진 연결 리스트에 사이클이 존재하는지 확인하세요.
사이클이 있다면 True를, 없다면 False를 반환해야 합니다.

---

문제 접근 방식 📋

1. 해시맵을 이용한 중복 검사:
   • 연결 리스트를 순회하면서 각 노드를 해시맵에 저장.
   • 노드가 이미 해시맵에 존재한다면 사이클이 존재한다고 판단.
2. 순회 종료 조건:
   • head가 None에 도달하면 사이클이 없다고 판단.

---

Solution 💻

# 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:
        pattern = {}
        while head:
            if head in pattern:
                return True
            else:
                pattern[head] = 1

            head = head.next

        return False

시간 복잡도 ⏲️

• 순회: 각 노드를 한 번씩 방문 (O(n)).
• 해시맵 탐색 및 삽입: 평균 (O(1)).
• 총 시간 복잡도: (O(n)).

공간 복잡도 🗄️

• 해시맵 공간: 최대 (O(n)) (n은 노드의 수).
• 총 공간 복잡도: (O(n)).

---

리팩토링 🛠️

개선된 코드 (플로이드의 토끼와 거북이 알고리즘)

# 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:
        slow, fast = head, head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

            if slow == fast:
                return True

        return False

리팩토링 후 시간 복잡도 ⏲️

• 순회: 두 포인터가 리스트를 순회하며 만날 때까지 진행 (O(n)).
• 총 시간 복잡도: (O(n)).

리팩토링 후 공간 복잡도 🗄️

• 추가 공간 사용 없음: 포인터 2개만 사용 (O(1)).
• 총 공간 복잡도: (O(1)).

---