LeetCode 141(Linked List Cycle, Python)

1. 문제 링크

• Linked List Cycle - LeetCode

Linked List Cycle - LeetCode

 

2. 문제 설명

• 주어진 연결 리스트(Linked List)가 사이클(고리)를 포함하는 지 판단하는 문제
• 리트 코드의 설명이 좀 이해가 어려운데 pos 는 어차피 입력값에 없으니 무시하고 사이클이 있는 지 판단하면 된다.
• 예시) 3 → 2 → 0 → -4 → 2 → 0 → -4 → ... 이면 2, 0, -4가 반복되는 사이클이 존재 

3. 처음 풀이 

• 처음 시도는 리스트를 순회하며 val을 seen=[]에 누적 저장하고, 이미 저장된 val이 등장하면 사이클이 있는 것으로 판단하였으나, 싸이클이 없어도 노드의 값이 중복해서 여러번 등장하는 경우가 있어 실패
• 직선 트랙과 원형 트랙으로 생각해보니 쉽게 풀림.
• 달리기가 빠른 사람과 느린 사람이 동시에 출발하면 직선 트랙에서는 절대 만날 수 없지만 원형 트랙에서는 언젠가 만날 수 밖에 없음.
• 따라서 사이클이 있다면 노드를 한칸씩 전진하는 경우와 두칸씩 전진하는 경우 언젠가 만날 수 밖에 없음.
• 전달된 head를 catcher에 저장한 후
• head는 head = head.next.next로 두칸씩 앞으로 가고
• catcher는 catcher=catcher.next로 한칸씩 앞으로 간다.
• 만약 head == catcher가 되는 순간이 생기면 사이클이 있는 것이고 그렇지 않고 head가 끝까지 도달하게 된다면 사이클이 없는 것이다.

# 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:
        catcher = head #head를 똑같이 catcher에 저장
        if not head or not head.next or not head.next.next:
            return False #사이클이 있다면 무한히 반복된다. head, head.next, head.next.next 중 None이 있으면 False
        while head and head.next and head.next.next:
            head = head.next.next #head를 두 칸 전진
            catcher = catcher.next #catcher는 한 칸 전진
            if head == catcher: #같은 순간이 있다면 원형 트랙, 사이클이 존재
                return True
        return False #그렇지 않고 head가 끝까지 가버린다면 사이클이 없다.

 

4. 다른 풀이 

• 사이클이 없다면 next를 반복하면 언젠가 head가 동이 나버려서 None이 된다.
• 사이클이 있다면 head를 계속해서 누적 저장해둔다면 언젠가 이미 저장된 head가 등장함
• 공간 복잡도는 O(n)이고 원래 풀이는 O(1)임

# 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:
        seen = set() #관찰한 head 저장
        while head: #head가 None이 아니면, 즉 남아 있다면
            if head in seen: #이미 나온 head라면 사이클이 존재
                return True
            else:
                seen.add(head) #처음 나온 head면 seen에 저장
            head = head.next #head 한칸 전진
        return False #head가 None이 나왔다면 False

5. 배운 점 

• 달리기로 이해해보는 아이디어

6. 관련 글

• 연결 리스트(Linked List)에 대한 글 : https://codingbubu.tistory.com/7