[2024] day 67. Leetcode 141. Linked List Cycle

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 3월 6일 (수)
Leetcode daily problem

141. Linked List Cycle

https://leetcode.com/problems/linked-list-cycle/description/

Problem

단방향 linked list의 head가 주어 질때, 해당 연결형 리스트가 순환하는 구조인지 아닌지 확인해서 cycle이 있으면 True, 없으면 False를 return 한다.

Solution

linked list, two pointer

주어진 단방향 링크드 리스트가 순회 하는지 아닌지 확인하기 위해서 포인터 두 개를 사용해서 확인하는 방법으로 문제를 해결한다.
하나의 포인터는 한 번에 한칸 이동, 다른 두번째 포인터는 한 번에 두칸을 이동하면서 링크드 리스트를 끝까지 탐색해 가는데 여기서 탐색하는 동안 순환한다면 빠르게 이동하고 있는 두 번째 포인터가 언젠간 하나의 포인터와 중첩되는 순간이 나오게 된다.

그러므로 두 번째 포인터가 끝에 도달해서 None이 되거나, 첫 번째 포인터랑 만날 때 반복을 종료 시키는데, 첫 번째 포인터와 만난다면 순환 구조라고 생각해서 True를 반환하고, 두 번째 포인터가 None 에 도달한다면 첫 번째 포인터와 만나지 않는 순환하지 않는 구조라 판단할 수 있기 때문에 False를 반환하면 된다.

Code

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

Complexicity

시간 복잡도

연결형 리스트의 모든 노드를 한 번씩 탐색하므로 시간 복잡도는 O(n)이 된다.

공간 복잡도

포인터로만 이동하기 때문에 다른 메모리를 차지 하지 않아 공간 복잡도는 O(1) 이다.