A Linked List is given with each node having two pointers. First pointer is pointing to the next node (just like in a single linked list). The second pointer points to any random node in the list. Write an algorithm to clone the given linked list in linear time.
Posted: Aug 16 '12
Seen: 96 times
Last updated: Aug 16 '12
We don't which one is the first pointer and which one is the second pointer... right ? are we allowed to use linear time (or) use single pass ?
Shiva Kintali (Aug 16 '12)editNode->next and Node->random are two pointers...so u know which one is which.
Nitesh Waghela (Aug 16 '12)editExtend the problem: one next and k random pointers (Node->next, Node->random_1, Node->random_2....., Node->random_K). Clone the list with N nodes.
Nitesh Waghela (Aug 16 '12)edit