Linked List Has Cycle

Solution 1

First solution is Floyd's tortoise anad hare algorithm. The idea is to move two different heads at different paces, if there is a cycle both should meet again in the future

If there is a loop both heads run forever and the algo returns something only when they meet

If there is no loop, the while loop ends and the function returns False

# Solution 1
def hasCycle(head: Optional[ListNode]) -> bool:
    # define the two heads
    slow, fast = head, head
    
    # while on the fast head as if there is no loop it will end first
    while fast:
        slow = slow.next
        fast = fast.next
        
        # if not at the end, fast head move to times faster than slow head
        if fast:
            fast = fast.next
            # if they meet return True
            if slow==fast:
                return True
            
    # if we reach the end hence there is no loop (otherwise heads would loop forever)
    return(False)

Solution 2

Second solution just stores the current head in a dict. If an head is already in the dict that means that we already visited it and hence it means that there is a loop in the linked list

# Solution 2
def hasCycle(head: Optional[ListNode]) -> bool:
    d = {}
    while head:
        if head in d:
            return(True)
        d[head] = 0
        head = head.next
    return(False)