Determine start of the cycle

Given a linked list with a cycle in it, detect the cycle and find the start node of the cycle

Solution

Find the cycle using fast ptr slow ptr approach

  • Set both pointers to the head of the list
  • Increment fast pointer by 2 and slow pointer by 1 each time
  • If we hit the end of the list then the list doesn't have a cycle
  • If fast ptr and slow ptr point to the same node then we have detected a cycle in the list

    def is_loop(head)
        return false if head == nil
        return false if head.ptr == nil
    
        slow_ptr = head
        fast_ptr = head
        fast_ptr = fast_ptr.ptr
        fast_ptr = fast_ptr.ptr
    
        while fast_ptr != nil && slow_ptr != nil do
          if slow_ptr == fast_ptr
            return true
          end
    
          slow_ptr = slow_ptr.ptr
          fast_ptr = fast_ptr.ptr
          fast_ptr = fast_ptr.ptr if fast_ptr != nil
        end
    
        return false
    end
    

Determine start of the cycle

  • Once the loop is detected, freeze the fast ptr and increment the slow ptr by 1 until it meets the fast ptr, this will tell us the length of the loop
  • Set the slow ptr to the head and increment the fast pointer until it is loop_length nodes away from the head
  • Now increment both pointers by 1 until they meet again, that will be the node at which the cycle starts

    slow_ptr = head
    fast_ptr = head
    
    // determined by freezing fast ptr
    // and incrementing slow ptr inside the loop
    loop_length = x
    
    while loop_length != 0
      fast_ptr = fast_ptr.next
      loop_length -= 1
    end
    
    while slow_ptr != fast_ptr
      slow_ptr = slow_ptr.next
      fast_ptr = fast_ptr.next
    end
    
    return slow_ptr
    

Time compelxity

O(n)

results matching ""

    No results matching ""