Wednesday, July 20, 2011

Merge of nodes

Two lists merge at some node. Find it in optimal time.
Pubblicato da a
Reazioni: 

2 comments:

  1. Find the length of both the lists - say n1 and n2. Without any loss of generality, assume n1>=n2.
    Let d=n1-n2.
    Travel d nodes in List 1. And then start travelling each node one by one in both the lists until you reach the node on wich the lists merge.

    Time complexity - O(n1+n2).

    Can we do better than this?

    ReplyDelete

Subscribe to: Post Comments (Atom)