Given a double linked list with one pointer pointing to the next node similar to single linked list. The second pointer can point to any node in the linked list. We have to write a program in O(n) time.
We can have a copy of the original nodes, create random links and separate original from cloned. This three step approach listed below.
We clone the copy of node in the original Linked List next to the original node.
2. We use the random pointer from the original nodes to add them in the copied node based on the next node.
3. Finally, we separate the original and cloned head.