Table of Contents
Given a doubly linked list, in which one pointer is pointing to the next node just like in a singly linked list.
The second pointer however can point to any node in the list.
Example
Method 1
Time Complexity : O(n)
Space Complexity : O(n)
In this method the main idea is to store the next and rand mappings of original list in an array first, then modify the original list to create a copy and then restore the original list.
Algorithm
1. Create all nodes in copy linked list using “next” pointers
2. Store the node and its “next” pointer mappings of original linked list in an array ie, to restore the original linked list
3. Change “next” pointer in original linked to point to the corresponding node in the copy linked list
4. Now, for all nodes in copy list point the “rand” pointer to the corresponding node
5. Finally, we will change the “rand” pointer for all nodes inย copy linked list as shown below
copy_list->rand = copy__list->rand->rand->next
6. Restore the next pointers in original list from stored mappings
The above algoorithm can be clearly explained in below diagram
Method 2
Time Complexity : O(n)
Space Complexity : O(1)
Algorithm
1. Create a copy of every node in the list and insert it in original list between current and next node
2. Now, copy the rand link in this fashion
original->next->rand = original->rand->next
This works because original->next is nothing but copy of original and original->rand is nothing but copy of rand.
3. Now restore the original and creating a copy linked lists in this fashion in a single loop.
original->next = original->next->next;
copy->next = copy->next->next;
Make sure that last element of original->next is NULL.