[LeetCode] 141. Linked List Cycle

말하는 감자·2024년 11월 29일
algorithmcycleleetcodelinked listpython리트코드링크드 리스트알고리즘자료구조코딩테스트코딩테스트 준비파이썬
1

LeetCode

목록 보기
17/32
post-thumbnail

이번 문제는 저번 문제와 마찬가지로 기본적인 링크드 리스트에 대한 이해가 확실하다면 쉽게 풀 수 있는 문제입니다.

그럼 살펴볼까요?

1. 오늘의 학습 키워드

  • Linked List
  • Cycle
  • Two Pointer

2. 문제: 141. Linked List Cycle

Description

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.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Constraints:

  • The number of the nodes in the list is in the range [0, $10^4$].
  • $-10^5$ <= Node.val <= $10^5$
  • pos is 1 or a valid index in the linked-list.

Follow up: Can you solve it using O(1) (i.e. constant) memory?

3. 문제 풀이

Step1. 문제 이해하기

주어진 연결 리스트의 head를 기준으로, 해당 연결 리스트에 사이클이 있는지 판별하는 문제입니다.

문제 예시를 보시면 head와 pos가 주어지는것처럼 보입니다. 하지만 문제에 다음과 같은 말이 적혀있습니다.

Note that pos is not passed as a parameter.

즉, pos는 주어진 함수 hashCycle의 매개변수로 전달되지 않습니다. 단지 테스트 데이터 구성을 돕는 역할이라 보면 될 것 같습니다.

우리는 주어진 연결 리스트에서 사이클 여부만 판별하면 됩니다.

정말 헷갈리죠? 다시 정리하자면,

문제에서 pos는 단순히 사이클의 위치를 설명하기 위해 사용된 설명용 매개변수입니다. pos를 활용해 사이클이 있는 리스트를 만들어야 할 필요는 있지만, 함수의 입력으로 주어지지 않기 때문에 hasCycle 함수 내에서는 이를 활용하지 않습니다.

pos는 테스트 케이스를 구성할 때 사이클을 만들기 위해 내부적으로만 필요합니다. 예를 들어, [3, 2, 0, -4]와 pos=1이 주어졌다면, 이는 노드 -4의 next 포인터가 노드 2를 가리키도록 설정하라는 의미입니다. 하지만 문제 자체의 요구사항은 노드 포인터를 따라가며 사이클을 판별하는 것이므로, hasCycle 함수의 구현에는 pos가 관여하지 않습니다.

그럼 이제 입력, 반환값들을 살펴보겠습니다.

  • Input:
    • 연결 리스트로 주어지는 노드의 개수는 0이상 10410^4개 이하입니다.
    • 따라서, O(n2)O(n^2)보다 효율적인 시간 복잡도로 코드를 구현해야 합니다.
    • 노드의 value는 −105-10^5 이상 10510^5이하입니다.
  • Output:
    • 주어진 연결 리스트에 사이클이 있으면 True, 없다면 False를 반환합니다.

문제는 이렇게 이해를 할 수 있을것 같습니다. 이제 좀 더 디테일하게 어떻게 구현하면 좋을지 분석으로 들어가보죠!!

Step2. 문제 분석하기

이 문제는 링크트 리스트가 주어졌을 때, 해당 연결 리스트의 사이클 여부를 확인하는 것입니다. 어느 위치의 노드에서 사이클이 아닌 tail노드에서 사이클의 유무를 확인하기 때문에 tail노드의 next가 없으면 사이클이 없으므로 False, 있다면 True를 반환하면 됩니다.

존재 유무를 판단하는 연산자는 다들 아실겁니다. 바로 in 연산자죠.

in 연산자가 O(1)로 작동하기 위해선 hash table, set이 필요합니다. 즉, tail노드가 나올때 까지 연결 리스트를 순회하면서, tail 노드의 next가 hash table에 없다면 False를 반환하면 되겠네요?

생각보다 문제 분석이 간단했습니다. 하지만 다른 방법이 또 있습니다.

바로 투 포인터를 활용하는 것입니다.

첫 번째 포인트는 한 칸식 이동하는 포인터, 두 번째 포인터는 두 칸씩 이동하는 포인터로 지정합니다. 이렇게 지정된 포인터를 이동시키면서 첫번째 포인터와 두 번째 포인터가 만나는 부분이 있다면 사이클의 존재를 파악할 수 있게 됩니다.

총 두 가 지 방법으로 문제 분석이 이뤄졌습니다. 이젠 이 방법들을 코드로 설계를 해보겠습니다.

Step3. 코드 설계

Hash Table

  1. 빈 set을 생성하여 순회 중 방문한 노드를 저장합니다.
  2. 현재 노드가 set에 존재하는지 확인합니다:
    • 존재하면 True 반환 (사이클 존재).
    • 존재하지 않으면 현재 노드를 set에 추가하고 다음 노드로 이동합니다.
  3. 리스트의 끝 (None)에 도달하면 False 반환 (사이클 없음).

Two Pointer

  1. slow와 fast 포인터를 헤드 노드로 초기화합니다.
  2. fast와 fast.next가 존재하는 동안 다음을 반복합니다:
    • slow를 한 칸 이동합니다.
    • fast를 두 칸 이동합니다.
    • slow와 fast가 같으면 True 반환 (사이클 존재).
  3. 반복이 끝나면 False 반환 (사이클 없음).

Step4. 코드 구현

Hash Table

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution(object):
    # # 1. Hash Table
    def hasCycle(self, head):
        # https://leetcode.com/problems/linked-list-cycle/submissions/1465481746
        """
        :type head: ListNode
        :rtype: bool
        """
        node_set = set()

        while head:
            
            if head in node_set:
                return True
            node_set.add(head)
            head = head.next
        
        return False

코드 설명:

  • node_set = set():
    • 노드들을 저장할 집합을 초기화합니다.
    • 집합은 삽입과 검색이 평균적으로 O(1)O(1)에 수행되므로 효율적입니다.
  • while head::
    • 리스트를 순회하기 위해 head가 None이 아닐 때까지 반복합니다.
  • if head in node_set::
    • 현재 노드가 이미 집합에 있는지 확인합니다.
    • 만약 head가 집합에 있다면, 이 노드는 이전에 방문했음을 의미하므로 사이클이 존재한다고 판단합니다.
  • node_set.add(head):
    • 현재 노드를 집합에 추가하여 방문 처리를 합니다.
    • 이후에 다시 이 노드를 만나면 사이클이 있다고 판단할 수 있습니다.
  • head = head.next:
    • 연결 리스트의 다음 노드로 이동합니다.
  • return False:
    • 리스트의 끝 (None)까지 도달한 경우, 사이클이 없으므로 False를 반환합니다.

시간 복잡도:

  • 시간 복잡도: O(n)O(n)
    • 각 노드는 한 번만 방문됩니다.
  • 공간 복잡도: O(n)O(n)
    • 최대 nn개의 노드를 set에 저장해야 합니다.

결과:

https://leetcode.com/problems/linked-list-cycle/submissions/1465481746

Two Pointer

# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution(object):
# # 2. Two Pointer
    def hasCycle(self, head):
        # https://leetcode.com/problems/linked-list-cycle/submissions/1465481577
        """
        :type head: ListNode
        :rtype: bool
        """
        first, second = head, head

        while second and second.next:
            first = first.next
            second = second.next.next

            if first == second:
                return True
        return False

코드 설명:

  • first, second = head, head:
    • 두 개의 포인터 first와 second를 초기화합니다.
    • first: 한 번에 한 칸씩 이동.
    • second: 한 번에 두 칸씩 이동.
  • while second and second.next::
    • second 또는 second.next가 None이면, 연결 리스트 끝에 도달한 것이므로 사이클이 없습니다.
    • 두 포인터가 계속 이동할 수 있는 동안 루프를 반복합니다.
  • first = first.next:
    • first 포인터는 한 번에 한 노드씩 이동합니다.
  • second = second.next.next:
    • second 포인터는 한 번에 두 노드씩 이동합니다.
  • if first == second::
    • 두 포인터가 동일한 노드를 가리킨다면, 이는 사이클이 존재함을 의미합니다.
    • first와 second는 처음에는 head에서 시작하며, 리스트가 사이클을 이루고 있다면 두 포인터는 반드시 만나게 됩니다.
  • return False:
    • second가 None에 도달한 경우, 리스트 끝까지 탐색한 것이므로 사이클이 없다고 판단합니다.

시간 복잡도:

  • 시간 복잡도: O(n)O(n)
    • 두 포인터가 한 번만 순회합니다.
  • 공간 복잡도: O(1)O(1)
    • 추가 메모리가 필요하지 않습니다.

결과:

https://leetcode.com/problems/linked-list-cycle/submissions/1465481577

4. 마무리

이번 문제는 기본적인 연결 리스트의 개념과 두 가지 접근 방식 (Hash Table, Two Pointer)을 활용한 문제입니다. Hash Table 방식은 직관적이지만 공간을 더 사용하며, Two Pointer 방식은 더 효율적인 메모리 사용이 가능합니다.

  • 배운 점:
    • set을 사용한 방문 확인 방법.
    • Two Pointer을 통한 효율적인 사이클 탐지.
  • 느낀 점:
    • 문제를 풀며 연결 리스트와 포인터의 개념을 다시 복습할 수 있었습니다.
    • Two Pointer 방식은 약간 더 복잡하지만 메모리 효율이 높아 실무에서도 유용할 것 같습니다.

앞으로도 다양한 연결 리스트 문제를 통해 더 깊이 학습해 보겠습니다!

테스트 케이스를 전부 실행하는 코드는 다음 링크에서 확인할 수 있습니다.

읽어주셔서 감사합니다!!

profile
말하는 감자
할 수 있다
이전 포스트

[LeetCode] 21. Merge Two Sorted Lists

다음 포스트

[LeetCode] 206. Reverse Linked List

0개의 댓글