[LeetCode]Linked List Cycle

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

Linked List Cycle - LeetCode

 

문제 분석

주어진 링크드 리스트에 사이클이 존재하는지 여부를 구하는 문제입니다.

 

처음 시도한 답안

# 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:
        # Set flag_val for past node.
        # [-10^5 <= Node.val <= 10^5] -> flag_val == 10^6
        flag_val = 10000000

        while head:
            # alreday traversal.
            if head.val == flag_val:
                return True
            
            head.val = flag_val
            head = head.next

        return False

접근 방법

1. 링크드 리스트를 끝날때까지 순회합니다.
2. 지나간 노드에 대해서는 flag_val을 설정합니다.
3. 반복이 끝날때까지 flag_val을 만나지 못했다면 싸이클이 없고, 만났다면 싸이클이 존재합니다.

가장 단순하게 링크드 리스트를 순회하면서 이전에 만난 노드가 있다면 싸이클이 존재하고, 없다면 싸이클이 존재하지 않는 방식으로 해결했습니다.

 

또한, 이 문제는 Hash Table 에 방문한 노드가 있는지 체크하는 방식과 fast(2칸씩 이동), slow(1칸씩 이동)를 활용한 투 포인터 방식으로도 해결할 수 있습니다.