Overlapping lists with cycle

Let hI and h2 be the heads of lists Ll and L2, respectively. Assume that L1 and L2 are may have cycles. Find if they are overlapping or not.

Solution

  • Determine if L1 has and L2 a cycle using fast_ptr-slow_ptr method

      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
    
  • If only one of them has a cycle then the lists cannot overlap

  • Only if both the lists have cycles then they can overlap and in that case they both must have the same cycle of nodes.
  • To determine if they have the same cycle, we must find the starting node of the cycle and verify its idential for both L1 and L2.

    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 complexity

O(n) for determining cycle in both lists O(n) to determine start of cycle and confirming the lists overlap. Overall complexity O(n).

results matching ""

    No results matching ""