Week 1-2. [Linked List] 141. Linked List Cycle (Python3)

문제 해결 과정

✍️ 나만의 방식으로 문제 정리하기 (=체계화)

https://leetcode.com/problems/linked-list-cycle/?envType=study-plan-v2&envId=top-interview-150

Linked List Cycle - LeetCode

주어진 연결 리스트에 사이클이 있다면 true, 없다면 false를 반환하라

• 입력
  • nodes | ListNode := 노드들, | nodes | ∈ [0, 10^4]
  • Node.val | int := 노드의 값, | Node.val | ∈ [-10^5, 10^5]
• 출력
  • hasCycle | boolean := 사이클을 가지고 있는지
• 조건
  • pos는 유효한 인덱스 혹은 -1이다.
    • pos는 사이클의 시작점이다.
    • pos가 -1이라면 사이클이 없는 것이다.

🔎 어떤 식으로 접근했는가?

링크드 리스트의 개념은 알고 있었지만, 알고리즘 문제는 처음 풀어보았기 때문에 어떻게 접근해야할 지 전혀 감이 잡히지 않았다.

첫 문제는 풀이를 확인하고 이후부터 혼자 풀어보기로 했다.

다른 사람의 코드를 탐구해보기

🎯 구현 코드

플로이드의 토끼와 거북이(Floyd's Tortoise and Hare) 알고리즘

한 칸씩 이동하는 slow 포인터와 두 칸씩 이동하는 fast 포인터, 두 개의 포인터를 이용해 사이클을 찾는다. (사이클이 있다면 두 포인터는 사이클 안에서 언젠가는 만난다.)

1. head부터 slow, fast 포인터를 각각 한 칸, 두 칸씩 이동시킨다.
2. 1번을 반복하다가, slow와 fast의 포인터가 같아진다면, 사이클이 존재하는 것이다.
3. 만약 slow 혹은 fast가 null에 도착한다면, 사이클이 존재하지 않는 것이다.

# 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:

        if head == None: return False
        
        slow, fast = head, head.next
        
        while slow != fast:
            if fast == None or fast.next == None: return False
            slow = slow.next # 한 칸 이동
            fast = fast.next.next # 두 칸 이동

        return True

 

⏱ 성능 측정 (시간복잡도/공간복잡도)

linear search이기 때문에 시간 복잡도는 O(N)이다.

또한 포인터(slow, fast) 두 개만 사용되기 때문에 공간 복잡도는 O(1)이다. 

 

느낀 점

알고리즘 문제는 종종 풀었지만 링크드 리스트 문제는 처음이라 매개변수로 head: Optional[ListNode]로 주어지는 것이 낯설었다.

토끼와 거북이 알고리즘도 처음 학습한 내용이었는데, 사이클의 유무를 판단할 때 slow와 fast 포인터를 사용하는 것도 알아두어야겠다!

 

참고 자료

Leetcode 141. Linked List Cycle with Python

LeetCode 연결 목록 주기 솔루션 설명 - Java

링크드 리스트에 사이클 찾기 (플로이드의 토끼와 거북이 알고리즘)