[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.
plzzz provide some hints
ReplyDeleteSuppose the original link is {A1, ..., A5} and the copied result is {B1, ..., B5}, which has the same structure.
ReplyDeleteThe 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..
Could you please elaborate on your approach? I didn't get the point where you say "merged link is split"?
ReplyDelete@Doom after first step Bi will be inserted between Ai and A(i+1).
ReplyDeleteso 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.
yes, got your logic. Thanks! :)
ReplyDelete