141.Linked-List-Cycle.md

141. Linked List Cycle

Difficulty: Easy

URL

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

Solution

Approach 1: Slow and fast pointers

The code is shown below:

# 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 not head or not head.next:
            return False
        slow_ptr = head
        fast_ptr = head
        while fast_ptr and fast_ptr.next:
            fast_ptr = fast_ptr.next.next
            slow_ptr = slow_ptr.next
            if fast_ptr == slow_ptr:
                return True
        return False

Approach 2: Hash Table

# 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:
        dc = set()
        cur = head
        while cur:
            if cur in dc:
                return True
            dc.add(cur)
            cur = cur.next
        return False