[LeetCode] 141. Linked List Cycle

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

Hash set based solution:

Time Complexity = O( N )

Space Complexity = O( N )

# 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:
        p = head
        memo = set()
        
        while p:
            if p in memo:
                return True
            else:
                memo.add(p)
                p = p.next
      

        return False

Fast and slow pointer solution:

Iterate the list with 'fast' and 'slow' pointers. If 'fast' pointer encounter 'slow' pointer, it means there is a cycle in the linked list.

Time Complexity = O ( N )

Space Complexity = O ( 1 )

# 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:
        fast, slow = head, head
        
        while fast and fast.next:
            if fast.next == slow:
                return True
            
            # 'fast' moves forward 2 steps
            fast = fast.next.next
            
            # 'slow' moves forward 1 step
            slow = slow.next
        
        return False