## Microsoft Interview Question

Software Engineer / Developers**Country:**United States

**Interview Type:**In-Person

Hi, I could not really understand what you meant by copy 1st node, insert between node 1 and node 2..

does it mean Original_node 1 --> copied node 1 --> Original_node2 again?

can you give an example as to how it works?

OriginalNode1 --> CopiedNode1 --> OriginalNode2 --> CopiedNode2 --> OriginalNode3 --> CopiedNode3 --> NULL

The above linklists merge as well as separation should be simple.

Now, lets say OriginalNode1 --> Arbitrary = OriginalNode3

So, as per the above Arbitrary pointer updation logic

Originalnode1 -->next --> Arbitrary (= CopiedNode1 --> Arbitrary) = OriginalNode1 --> Arbitrary --> next (= OriginalNode3-->next = CopiedNode3)

which is essentially same as CopiedNode1 --> Arbitrary = CopiedNode3

And so on....

I got the same question in microsoft coding round, but I did it in the other way which is not so efficient... Thanks for this great idea.... :)

Does it require the extra space when you separate and return the newly created (copied) linkedlist

I am not sure, but usually the input for the Copy/Clone is a const, so you cannot insert nodes in the original list , as described in this algorithm. Can this problem be solved with this additional restriction?

Simple implementation for described idea :

```
static Node Clone(Node head)
{
if (head == null) return null;
Node doubledHead = head;
// double original list
while (head != null)
{
Node next = head.Next;
Node copy = new Node { Value = head.Value, Next = head.Next };
head.Next = copy;
head = next;
}
// set random link
Node originalRunner = doubledHead;
while (originalRunner != null)
{
originalRunner.Next.Random = originalRunner.Random == null ? null : originalRunner.Random.Next;
originalRunner = originalRunner.Next.Next;
}
// seperate lists
Node copyHead = doubledHead.Next;
Node copyTail = null;
while (doubledHead != null)
{
Node copyNode = doubledHead.Next;
if (copyTail != null) copyTail.Next = copyNode;
copyTail = copyNode;
doubledHead = doubledHead.Next.Next;
}
return copyHead;
}
```

here is the c++ version of it

```
node* deepcopy()
{
if(!this->head) return NULL;
node* cur = this->head;
while(cur) {
node* cpy = new node(cur->val, cur->next, cur->random);
cur->next = cpy;
cur = cpy->next;
}
node* newHead = this->head->next;
cur = newHead;
while(cur) {
// resolve random's copy position
cur->random = cur->random != NULL ? cur->random->next : NULL;
// move two nodes further
if(cur->next){
cur = cur->next->next;
} else {
break;
}
}
// fix original list and seperate them again
cur = this->head;
while(cur) {
node* tmp = cur->next;
if(cur->next){
cur->next = cur->next->next;
cur = tmp;
} else {
break;
}
}
return newHead;
}
```

sd's method is very innovative but will require extra space in the old list (adding nodes in the list). Here is an alternate method which does not use extra space in the old list:

1. Duplicate the list, change newnode->random to point to node->next, change node->next to point to newnode. e.g.:

```
node = head;
while(node!=null)
Node newnode = new Node(node);
Node* next_node = node.next;
newnode.random = next_node ; //preserve the relationship of the old nodes
node.next = newnode;
node = next_node;
```

2. Iterate through both lists, fill in the random pointer and recover the old list

```
newnode = newhead;
node = head;
while(newnode!=null)
Node* tmp = newnode.random; //this stores the next node in the old list
newnode.random = node.random.next;
//revert the old node back
node.next = tmp;
node = node.next;
newnode = newnode.next;
```

The solution from sd should work fine and it is very creative.

Another solution can be,

1. It will create a duplicate linked list. But ->next of the original list will point equivalent node in the new linkedlist.

node* pOld = head;

node* pNew = Null;

node* pNewTail = Null;

while (pOld)

{

if (pNewTail == null)

{ pNew=pNewTail = new node; pNew->val = pOld->val; }

else

{

pNewTail->next = new node;

pNewTail->next->val = pOld->val;

pNewTail = pNewTail->next;

}

node* pCurrent = pOld;

pOld = pOld->next;

pCurrent = pNewTail;

}

2. Then update random pointer of the new linkedlist

node* pOld = head;

while (pOld)

{

pNew->random = pOld->random->next;

pNew = pNew->next;

pOld = pOld->next;

}

I totally did not get what your code is doing. pOld->random is supposed to be a node in the linkedlist, whose next is another node right behind it. I did not see you modify the next pointer. Besides, you cannot trace the nodes by random pointer, what if some nodes` random pointers are NULL?

node *temp=head;

create_list(node *temp){

node *n;

n=new node;

if(temp->next!=NULL){

create_list(temp->next);

}

n->next=temp->next;

n->rand=temp->rand;

}

Iterate over the linkedList and create a copy of each node with following changes:

if we make n' as duplicate of node n:

1. n'.random=n.random

2. n.random=n'

Now we iterate over the lists one more time and for every node-duplicate pair:

1. temp=n'.random

2. n'.random=temp.random

3. n.random=temp

This works in O(n).

I am not sure i got the what this question is asking for entirely. why can not one copy the linked list based on the next pointer first and fix up the random node pointer after the linked list is copied.

After copying the list based on the next pointer, when you try to copy the random pointers, you don't know that is the correct element pointer by the random pointer in the cloned list.

yes, you can, but it takes time coz u need to compare original->random to all other nodes in that list and as you are moving in the other list also,

1. copy the 1st node and insert it between node 1 & node 2

- sd September 14, 20133. Similarly, copy 2nd node and insert it between 2 & 3.. and so on

2) Copy the arbitrary link in this fashion

Originalnode->next->arbitrary = Originalnode->arbitrary->next;

and so on...for all nodes

3) Separate the original and copy linked lists.