Microsoft Interview Question
Software Engineer / DevelopersCountry: 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.