[Leetcode/파이썬] 141. Linked List Cycle

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.

 

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

 

Constraints:

• The number of the nodes in the list is in the range [0, 104].
• -105 <= Node.val <= 105
• pos is -1 or a valid index in the linked-list.

 

Follow up: Can you solve it using O(1) (i.e. constant) memory?

 

# 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:
        fast = head
        slow = head

        while fast and fast.next :
            fast = fast.next.next
            slow = slow.next
            if fast == slow :
                return True

        return False

문제는 이 리스트가 사이클을 형성하고 있는지 아닌지를 묻는 문제이다. 이거 어떻게 풀어... 라고 생각했는데, 풀이를 보니 생각보다 단순해서 쉽게 이해할 수 있었다.

사이클을 확인하는 방법은 간단하다. 두 개의 더미 노드를 준비하자. 풀이 코드에서는 slow, fast 같이 2개로 준비했다. 이름 답게 하나는 2칸씩 이동, 하나는 1칸씩 이동을 하게 했다. 하나의 더미노드가 끝에 도달할 때 까지 진행을 하였다. 만약 사이클이 형성되어 있다면 이 while 루프는 끝나지 않을 것이다.

정답처리로는 while 루프 중 fast 포인터와 slow 포인터가 같은 곳을 가리키면 이 리스트는 사이클을 형성하고 있다고 판단할 수 있다. 루프를 도는 와중에는 언젠가는 만날 수 밖에 없기 때문에 이런 풀이가 가능한 것이다.