[알고리즘/Python] LeetCode 141. Linked List Cycle

📑 1. 문제 이해

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

Linked List Cycle - LeetCode

이 문제는 연결리스트에서 싸이클이 존재하는지 판별하는 문제입니다. 연결리스트의 노드는 하나도 없을 수 있고, 최대 10 ^4개일 수 있습니다. 노드의 값은 음수일 수도 있으며, 그 값은 중복될 수 있습니다.

☑️ 테스트케이스

문제에서 주어진 테스트케이스는 다음과 같습니다.

 

1) Example1:  Head = [3,2,0,-4], pos = -1 

   - 싸이클이 존재하지 않습니다.

2) Example2:  Head = [1,2], pos = 0

   - 마지막 노드가 첫번째 노드를 가리키는 원형 연결리스트입니다.

3) Example3:  Head = [1], pos = [-1]

   - 노드가 총 한개이고 싸이클이 존재하지 않습니다.

 

추가해서 생각해봐야할 테스트케이스는 다음과 같습니다.

 

4) Head = None, pos = [-1]

   - 노드가 0개로 빈 연결리스트 입니다.

 

이때 주의할 것은 실제 매개변수로 들어오는 것은 l1, l2배열이 아니라, 연결리스트의 head라는 점입니다. 즉 채점시에는 다음과 같이 input 배열을 연결리스트 형태로 반환한 후 그 연결리스트를 사용해 우리가 제출한 답안을 테스트할 것입니다.

class ListNode:
    def __init__(self, val, index):
        self.val = val
        self.next = None
        self.index = index

def makeLinkedList(arr: List[int], pos:int) -> ListNode:
    head = ListNode(float('inf'), None)
    prev = head
    
    for i, n in enumerate(arr):
        prev.next = ListNode(n, None, i)
        prev = prev.next
        
    if pos != -1:
       # index가 pos인 node에 연결.
       prev.next = getNode(pos)
       
    return head.next

head = makeLinkedList([2, 4, 3], 0)

Solution.hasCycle(head)

💡 2. 알고리즘 설계

싸이클이 있다면 한번 방문한 노드를 다시 방문하게 됩니다. 검색이 빠른 set 자료형을 사용해 방문한 노드를 기록해둡니다. 중복된 값이 있을 수 있기 때문에 노드의 값이 아닌 노드 객체그 자체, 노드 객체의 주소값을 기록합니다. 만약 한번 방문한 노드를 다시 방문한다면 싸이클이 있다는 의미로 True를 반환합니다. 모든 노드 방문이 끝나서 curr이 더 이상 유효한 노드를 가리키지 않는다면 반복문은 종료됩니다. 싸이클이 없다는 의미이므로 False를 반환합니다.

def hasCycle(head: ListNode) -> bool:
    visited = set()
    curr = head
    while curr:
        if curr in visited:
            return True
        visited.add(curr)
        curr = curr.next
    return False

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 모든 노드를 최대 한번 방문합니다.

공간 복잡도: O(N). 싸이클이 없다면 모든 노드가 set에 기록됩니다. 따라서 노드의 개수만큼의 공간이 필요합니다.

 ⎌ 4. 검토

테스트 케이스를 검토해보면 다음과 같습니다.

 

1) Example1:  Head = [3,2,0,-4], pos = -1

   - 싸이클이 존재하지 않기때문에 중복해서 노드를 방문하지 않고 반복문이 종료됩니다. False가 반환됩니다.

2) Example2:  Head = [1,2], pos = 0

   - 1-> 2-> 1순으로 방문해 중복 방문이 되므로 True가 반환됩니다.

3) Example3:  Head = [1], pos = [-1]

  - 싸이클이 존재하지 않기때문에 중복해서 노드를 방문하지 않고 반복문이 종료됩니다. False가 반환됩니다.

 

추가해서 생각해봐야할 테스트케이스는 다음과 같습니다.

 

4) Head = None, pos = [-1]

   - curr은 처음부터 None을 가리키므로 반복문이 실행되지 않고 바로 False가 반환됩니다.

---

🤔 다른 사람의 풀이

일명 토끼와 거북이 알고리즘인 Floyd's Cycle Detection 알고리즘을 사용해 싸이클이 있는이 판단할 수 있습니다. 이 알고리즘은 싸이클이 있는 경우 토끼가 두바퀴를 빨리 돌아 거북이를 따라잡을 수 있다는 아이디어를 활용한 것입니다.

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        s = f = head

        while f and f.next:
            s = s.next
            f = f.next.next
            if f == s:
                return True
        return False

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N). 싸이클이 없다면 연결리스트의 모든 노드를 한번만 방문하고, 사이클이 있다면 각 노드는 최대 두번 방문되고 while문은 최대 N번 반복됩니다.

공간 복잡도: O(1).두 개의 포인터를 제외한 추가 공간은 필요하지 않습니다.

---

✅ 정리

◎ 연결리스트의 싸이클은 플로이드의 순환 판별 알고리즘으로 판별할 수 있고, 그래프의 싸이클은 disjoint-set 알고리즘으로 판별할 수 있습니다.

◎ 만약 특수한 알고리즘이 떠오르지 않는다면 기본 자료형을 사용한 가장 간단한 알고리즘을 떠올릴 수 있어야합니다.