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).