[Amazon]clone a linked list with random pointer

You are given a Double Link List with one pointer of each node pointing to the next node just like in a single link list. The second pointer however can point to any node in the list and not just the previous node. Now write a program in O(n) time to duplicate this list. That is, write a program which will create a copy of this list.


  1. plzzz provide some hints

  2. Suppose the original link is {A1, ..., A5} and the copied result is {B1, ..., B5}, which has the same structure.

    The first step is to create and insert new nodes after the original node. The {Ai, Bi} can be treated as a group and all operations are done on those groups.
    The next step is to mirror the extra link from Ai to Bi.
    Finally, the merged link is split into two separate links. The newly created link list has the same structure as in the original one...try this on paper..

  3. Could you please elaborate on your approach? I didn't get the point where you say "merged link is split"?

  4. @Doom after first step Bi will be inserted between Ai and A(i+1).
    so we create a link from Ai to Bi and Bi to A(i+1).

    //here link is head of list
    LinkNode p = link;
    do {
    LinkNode p2 = new LinkNode();
    p2.value = p.value();
    p2.next = p.next;
    p.next = p2;
    p = p2.next;
    } while (p != null);

    Then, extra arbit link in the A's will be copied as it is in group of B's.

    p = link;
    do {
    if (p.extra != null) {
    p.next.extra = p.extra.next;
    p = p.next.next; // NOTE: p = p.next.next;
    } while (p != null);

    so extra link will also be copied now we just want to revert the changed made in step 1.

    p = link;
    LinkNode link2 = p.next;
    while (p.next != null) {
    LinkNode q = p.next;
    p.next = q.next;
    p = q;

    Hope you understand,do comment.

  5. yes, got your logic. Thanks! :)


Post a Comment

Popular posts from this blog