Wednesday, July 20, 2011

Merge of nodes

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

2 comments:

  1. UnknownAugust 1, 2011 at 1:45 AM

    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
  2. codingplaygroundAugust 4, 2011 at 3:15 AM

    no

    ReplyDelete

Subscribe to: Post Comments (Atom)