(leetcode 문제 풀이) Linked List Cycle

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.

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

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head:
            return False
        if not head.next:
            return False
        
        first = head
        second = head
        while first != None and first.next != None:
            first = first.next.next
            second = second.next
            if first == second:
                return True
        return False

Linked list가 싸이클이 있는지 없는지 여부를 판단하는 문제다. 코드 로직은 비교적 간단한데, 싸이클 유무를 판별하기 위해 노드 A의 옆 노드와 노드 B의 옆 옆 노드가 같은지 계속 확인하는 것이다. 위의 예시를 살펴보면, 노드 0의 next의 next는 노드 2가 된다. 그리고 노드 -4의 next는 노드 2가 된다. 따라서 싸이클이 존재한다고 이야기할 수 있는 것이다.

이는 사실 모든 노드를 살펴보면서 싸이클이 마지막 노드에 있다면 결국 이 논리가 끝까지 성립되기 때문에 True가 리턴된다. 따라서 시간 복잡도는 $O(N)$이 걸리게 된다.