LeetCode Top Interview 150) Linked List Cycle

Question

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:

• The number of the nodes in the list is in the range [0, 10^4].
• -10^5 <= Node.val <= 10^5
• 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: Optional[ListNode]) -> bool:

---

---

주석으로 주어진 ListNode의 첫 노드가 head로 들어옵니다.

• head는 리스트가 아닙니다. 어떤 링크드리스트의 헤드 노드입니다.
• pos는 입력으로 주어지는 것이 아닌 마지막 노드가 가리키는 특정 ListNode입니다.

이 때 해당 링크드리스트가 사이클 구조, 즉 순환하는 구조가 존재하는지 확인하여 결과에 따라 bool값을 반환하는 문제입니다.

제가 생각한 코드는 다음과 같습니다.

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

        while head.val != 'pass':
            if head.next==None:
                return False
            head.val = 'pass'
            head = head.next
        return True

• 입력값 head가 비어있다면 False를 반환하여 빈 입력값 예외를 처리합니다.
• 현재 head값이 pass가 나오지 않을때까지 링크드리스트를 순회합니다.
  • 다음 노드가 없어서 None이라면 순환하지 않고 끊기므로 False를 반환합니다.
  • 탐색한 head의 값을 pass로 바꿉니다.
    • 원래값을 바꾸는 것은 당연히 좋지않은 코딩 방식이지만 문제에서 공간복잡도를 O(1)으로 확인하는 방법을 추가로 요구했기에 생각해본 방법입니다.
    • 원래대로면 집합을 사용하여 이미 나온 값을 통해 순환을 확인할 수 있겠습니다.
    • 지금 생각해보니 노드의 val값의 범위가 정해져있으니 집합도 O(1) 방법으로 볼 수 있겠네요..?
  • 다음 노드를 head로 다시 저장합니다.
    • 이 방법도 메모리 사용을 최소화한 방법이라 head를 반복해서 사용하는거지 가독성을 위해서는 굳이 head를 재사용하지않고 새로운 변수 node등을 선언하는 것이 좋다고 생각합니다.
• 만약 새로운 head가 pass값을 가지고 있다면 반복문을 탈출합니다. 이는 순환된 구조를 가진것이므로 True를 반환합니다.

---

문제가 어렵진 않았습니다. 아주 예전에 클래스나 포인터 개념이 부족했을 때 기본적인 부분에서 많이 헤메었던 기억이 났네요.
링크드리스트와 클래스의 기본 개념만 잡혀있다면 크게 고민할 부분은 없던 문제라 생각합니다!