Create a duplicate copy of the Linked List in O (n) time

Question

The list of links is specified with two pointers, the first points to the next node, and the other points to a random pointer. A random pointer points to any LinkedList node. Write a complete program to create a copy of Linked List (c, C ++, C #) without changing the original list and in O (n).

I was asked this question in an interview, and I could not understand the solution. Help will be appreciated.

Answer 1

Copying a regular linked list in linear time is obviously trivial. The only part that makes this interesting is the "random" pointer. Presumably, by "random" you really mean that it points to another randomly selected node in the same linked list. Presumably, it is assumed that a copy of the linked list recreates exactly the same structure, i.e. The “next” pointers create a linear list, and the other pointers refer to the same relative nodes (for example, if a random pointer in the first node of the source list points to the fifth node in the source list, then a random pointer in the duplicate list also points to the fifth node of the duplicate list .

Doing this in N ² time is pretty simple. Duplicate the list first, usually ignoring the random pointer. Then go through the source list one node at a time, and for each node again scroll through the list to find which node of the list the random pointer refers to (i.e. how many nodes you go through next to find the next pointer containing that same address as the random pointer of the current node.Then go through the duplicate list and cancel it: find N ^th node, and put this random pointer in the current node.

The reason for this is O (N ² ), first of all, it is a linear search for the right nodes. To obtain O (N), these searches must be performed with constant complexity instead of linear complexity.

The obvious way to do this is to build a hash table that maps the address of each node in the source list to the position of that node in the list. Then we can build an array containing the addresses of the nodes in the new list.

With this, fixing random pointers is pretty simple. First, we look at the source list using next pointers, duplicate nodes and create our new list, linked using next pointers, but leaving only random pointers. As we do this, we insert the address and position of each node in the hash table and the address of each node in a new list in our array.

When we are done with this, we will go through the old list and the new list in lock mode. For each node in the old list, we look at the address in this node with a random pointer. We look at the position associated with this address in our hash table, then we get the node address in the new list at this position and put it in the random pointer of the current node in the new list. Then we move on to the next node in both the old and the new list.

When we are done, we discard / destroy both the hash table and the array, since our new list now duplicates the structure of the old one and we no longer need additional data.

Answer 2

Approach Overview
We will not try to create a new linked list directly from the word go. Duplicate the items in the original linked list first, then divide the list into 2 identical lists.

Details
Step 1 Run the linked list using the following pointers and duplicate each node.

 original :: A -> B -> C -> D -> E ->null updated :: A -> A' -> B -> B' -> C -> C' -> D -> D' ->E -> E' -> null 

This can be easily done in one cycle.

Step 2 : move the list again and fix random pointers like this

 Node *current= start; Node *newListNode, *random; while (current!= null) { // If current node has a random pointer say current = A, A.random = D; if ( (*current)->random != null ) { // newListNode will point to A' newListNode = (*current)->next; random = (*current)->random; random = (*random)->next; // Make A' point to D next, which is D' (*newListNode)->random = random; } // Here A'.random = D' // Current goes to the next node in the original list => B , and not A' current= (*newListNode)->next; } 

Step 3 Divide the list into 2 lists. You just need to fix the following pointers here.

 Original :: A -> A' -> B -> B' -> C -> C' -> D -> D' ->E -> E' -> null New :: A -> B -> C -> D -> E ->null A' -> B' -> C' -> D' -> E' ->null Node *start1 = head; Node *start2 = (*head) ->next // Please check the boundary conditions yourself, // I'm assuming that input was a valid list Node *next, *traverse = start2; while (traverse != null) { next = (*traverse)->next; if (next == null) { (*traverse)->next = null; break; } (*traverse)->next = (*next)->next; traverse = next; } 

So you created a copy of the original list in O (n) time. You move the list 3 times, which is still n order.

Answer 3

Editing Refinement:

The following only works if the "random" pointers are unique, as BowieOwens pointed out.
I leave the answer only for a general idea, but please do not increase how much this is definitely wrong .

---

If I'm not mistaken, you can do this without using additional storage.

When you copy the old list, store the random pointer from the old node in the random pointer of the new node.
Then set the random pointer of the old node to the new node.

This will give you a zig-zag structure between the old list and the new list.

pseudo code:

 Node* old_node = <whatever>; Node * new_node = new Node; new_node->random = old_node->random; old_node->random = new_node; 

Once you have copied the old list, you start all over again, but replace the random pointers as follows, restoring the pointers in the old list, setting the random pointers in the new list to the corresponding new nodes:

 Node* old_random = old_node->random->random; // old list -> new list -> old list Node* new_random = new_node->random->random; // new list -> old list -> new list old_node->random = old_random; new_node->random = new_random; 

It looks a lot better on paper, but I'm afraid my ASCII art skills are not up to it.

This changes the original list, but is restored to its original state.
As far as I understand, it depends on the interview.

Answer 4

As you should know, O (n) means linear. Since you need a copy of the linear data structure, you will not have problems with it, since you just need to iterate over the nodes of the source list, and for each node visited, you will create a new node for the new list. I think the question is not well worded, because you need to know some aspects to complete this work: is it a circular implementation? What is the next node? The next node from the node or the 1st node of the list? How does the list end?

Answer 5

Perhaps this question is a trick to check how you answer for a strange question, because it is very simple:

1) Iterate to each node

2) Create a new node for another linked list and copy it.

The cost is always O (n): because you just iterate over the entire linked list only 1 time !!!

Or do you understand something is wrong with his question.