Problem description:
There is a single linked list where we need to duplicate the entire list. One challenge here is that along with next pointer there is another pointer called random pointer. This random pointer will point to some random node in the list. This random pointer can be NULL or itself or any other node in the list.
So cloned list should also have the random pointer it should point to the new node corresponding to the existing random node. This is the main expectation from the problem.
Every problem has different approaches to solve. The solutions are great. I am getting the final optimized solution only after seeing the solutions.
Before exploring the existing solutions, I tried two approaches:
- One with the hash table. Here I used UT hash library. This has additional memory overhead.
- Another with traversing each time for learning random node. This solution has overhead of traversal for each random node.
Hash table based solution 1: One while loop to go through the list using next pointers and add it hash table. Next while loop to go through list using next pointers, in a loop get the random pointer and fill.
struct hnode{
struct Node *key;
struct Node *val;
UT_hash_handle hh;
};struct Node* copyRandomList(struct Node* head) {
struct Node *nh, *tmp, *node,*nlt,*rt;
struct hnode *ht = NULL, *hn, *nrt;
if (!head)
return NULL;
tmp = head->next;
node = (struct Node *)calloc(1, sizeof(struct Node));
node->val = head->val;
nh = node;
nlt = nh;
hn = (struct hnode *)malloc(sizeof(struct hnode));
hn->key =head;
hn->val = nh;
HASH_ADD_PTR(ht, key, hn);
while (tmp){
node = (struct Node *)calloc(1,sizeof(struct Node));
node->val = tmp->val;
hn = (struct hnode *)malloc(sizeof(struct hnode));
hn->key =tmp;
hn->val = node;
HASH_ADD_PTR(ht, key, hn);
nlt->next = node;
nlt = nlt->next;
tmp = tmp->next;
}
tmp = head;
nlt = nh;
//filling the random pointers
while (tmp&&nlt){
rt = tmp->random;
if (!rt) nlt->random = NULL;
else if (rt==tmp) nlt->random = nlt;
else {
HASH_FIND_PTR(ht, &rt, hn);
if (!hn){
printf("entry not there in ht , this condition should not come\n");
}
nlt->random = hn->val;
nlt->random = nrt;
}
tmp = tmp->next;
nlt = nlt->next;
}
return nh;
}
Hash table based solution 2: One while loop to go through the list using next pointers. Find the corresponding next pointer in hash table, if not create and add it.
Find the corresponding random pointer in hash table, if not create and add it.
Compared to above approach, 2 find operations added as the code is consolidated into one while instead of two. But I felt its not a clean approach as an overhead of additional hash-find operation.
struct hnode{
struct Node *key;
struct Node *val;
UT_hash_handle hh;
};struct Node* copyRandomList(struct Node* head) {
struct Node *nh, *tmp, *node,*nlt,*rt, *nrt;
struct hnode *ht = NULL, *hn;
if (!head)
return NULL;
tmp = head->next;
node = (struct Node *)calloc(1, sizeof(struct Node));
node->val = head->val;
nh = node;
nlt = nh;
hn = (struct hnode *)malloc(sizeof(struct hnode));
hn->key =head;
hn->val = nh;
HASH_ADD_PTR(ht, key, hn);
/* fill the random node simultaneously */
rt = head->random;
if (!rt) nh->random = NULL;
else if (rt==head) nh->random =nh;
else{
node = (struct Node *)calloc(1, sizeof(struct Node));
node->val = rt->val;
nh->random = node;
hn = (struct hnode *)malloc(sizeof(struct hnode));
hn->key =rt;
hn->val = node;
HASH_ADD_PTR(ht, key, hn);
}
while (tmp){
/* search for next pointer */
HASH_FIND_PTR(ht, &tmp, hn);
if (hn){
nlt->next = hn->val;
node = hn->val;
}else {
node = (struct Node *)calloc(1,sizeof(struct Node));
node->val = tmp->val;
hn = (struct hnode *)malloc(sizeof(struct hnode));
hn->key =tmp;
hn->val = node;
HASH_ADD_PTR(ht, key, hn);
nlt->next = node;
}
/* filling rand pointer */
rt = tmp->random;
if (!rt) node->random = NULL;
else if (rt==tmp) node->random =node;
else{
/* search for random pointer */
HASH_FIND_PTR(ht, &rt, hn);
if (hn){
node->random = hn->val;
}else {
nrt = (struct Node *)calloc(1, sizeof(struct Node));
nrt->val = rt->val;
node->random = nrt;
hn = (struct hnode *)malloc(sizeof(struct hnode));
hn->key =rt;
hn->val = nrt;
HASH_ADD_PTR(ht, key, hn);
}
}
nlt = nlt->next;
tmp = tmp->next;
}
return nh;
}
My next approach is no hash table but traversal:
struct Node *get_rand_traversals(struct Node *head,
struct Node *rand_node,
struct Node *nhd);
struct Node* copyRandomList(struct Node* head) {
struct Node *nh, *tmp, *node,*nlt,*rt;
struct hnode *ht = NULL, *hn, *nrt;
if (!head)
return NULL;
tmp = head->next;
node = (struct Node *)calloc(1, sizeof(struct Node));
node->val = head->val;
nh = node;
nlt = nh;
while (tmp){
node = (struct Node *)calloc(1,sizeof(struct Node));
node->val = tmp->val;
nlt->next = node;
nlt = nlt->next;
tmp = tmp->next;
}
tmp = head;
nlt = nh;
//fill the random pointers
while (tmp&&nlt){
rt = tmp->random;
if (!rt) nlt->random = NULL;
else if (rt==tmp) nlt->random = nlt;
else {
nrt = get_rand_traversals(head, rt, nh);
nlt->random = nrt;
}
tmp = tmp->next;
nlt = nlt->next;
}
return nh;
}struct Node *get_rand_traversals(struct Node *head,
struct Node *rand_node,
struct Node *nhd){
struct Node *tmp = head, *nt = nhd;
while (tmp!=rand_node){
tmp = tmp->next;
nt = nt->next;
}
return nt;
}
Next learned solution:
This is really awesome. No hash table, no extra traversal.
The approach is :
- For each existing node in the list, create another node and insert next to it.
So while going through the next pointers , at the end, list is doubled with new pointers. - In next while loop, go through existing nodes and newly added nodes simultaneously. Get the random nodes of existing nodes and assign the next node of random nodes to the newly added nodes.
- In next while loop, separate the lists with old nodes and new nodes.
Below is the solution:
struct Node* copyRandomList(struct Node* head) {
struct Node *nh, *tmp, *node,*nlt,*rt;
struct hnode *ht = NULL, *hn, *nrt;
if (!head)
return NULL;
tmp = head->next;
node = (struct Node *)malloc(sizeof(struct Node));
node->val = head->val;
nh = node;
nlt = nh;
nlt->next = tmp;
head->next = nh;
while (tmp){
node = (struct Node *)malloc(sizeof(struct Node));
node->val = tmp->val;
nlt = tmp->next;
tmp->next = node;
node->next = nlt;
tmp = nlt;
}
tmp = head;
nlt = nh;
//filling the random pointers
while (nlt){
rt = tmp->random;
if (!rt)
nlt->random = NULL;
else
nlt->random = rt->next;
tmp = tmp->next->next;
if (nlt->next)
nlt = nlt->next->next;
else
nlt = NULL;
}
/* forming a new list and keeping back the new list */
nlt = nh;
tmp = head;
while (nlt){
if (nlt->next)
nrt = nlt->next->next;
else
nrt = NULL;
rt = tmp->next->next;
tmp->next = rt;
nlt->next = nrt;
tmp = rt;
nlt = nrt;
}
return nh;
}Please provide your comments.
