Sid
BAN USER//given start of linked list : start;
*pointer start,start',nextNode,nextNode';
// each node conatin one pointer 'next' and another 'rand' with obvious purposes.
//Part 1 : create clone linked list where rand pointer of each clone is pointing to element pointed by original element of that clone,
// and rand pointer of each original node pointing to its cloned node.
nextNode = start;
start'=null;
while(nextNode!=null){
if(start'==null){
start' = createClone(nextNode);
nextNode'=start';
}
else{
nextNode'->next=createClone(nextNode); //createClone creates a memory for similar node pointer having value as
//argument node and next pointer pointing to null;
nextNode'=nextNode'->next;
}
nextNode'->rand=nextNode->rand;
nextNode->rand=nextNode';
nextNode=nextNode->next;
}
//Part 2 : Point next pointer of each clone to the rand element of respective original nodes
// and rand pointer of each clone to point to cloned rand node
nextNode=start;
nextNode'=start';
while(nextNode!=null){
*pointer temp = nextNode'->next;
nextNode'->next=nextNode'->rand;
nextNode'->rand=nextNode'->rand->rand;
nextNode=nextNode->next;
nextNode'=temp;
}
//Part 3 : Point each original node 'rand' pointer to original rand node,
// and clone node's next pointer to next cloned node.
nextNode=start;
nextNode'=start';
while(nextNode!=null){
nextNode->rand=nextNode'->next;
nextNode'->next=nextNode->next->rand; //null check the value and assign null if nexttNode->next is null;
nextNode=nextNode->next;
nextNode'=nextNode'->next;
}
So, finally
start : pointer to original linked list and
start' : pointer to cloned linked list.
Time complexity of each part(3 parts) is : exactly n.
- Sid February 06, 2012So, total time complexity of this algorithm is 3n, which is way less that O(n^2).