Problem: Given a Linked List with one pointer of each node pointing to the next node and the second pointer can point to any node/ random node in the list . Write a program which to make a copy of this list.
Solution:
Solution:
- Create the copy each node in the list and insert it between node and its next.
- Now copy the random pointer as follows:
- node->next->random = node->random->next
- Restore the original and copy linked lists as follows:
- original->next = original->next->next
- copy->next = copy->next->next
Implementation:
List* List::copy()
{
if (head == null)
{
return new List(); // empty list
}
ListNode * itr = head;
while(itr)
{
itr->next = new ListNode(itr->data, itr->next);
itr = itr->next->next;
}
itr = head;
while(itr)
{
itr->next->random = itr -> random ? itr->random->next : null; // random could be null
itr = itr->next->next;
}
itr = head;
ListNode* copyHead = head->next;
ListNode* copyItr = copyHead;
while(copyItr->next)
{
itr->next = itr->next->next;
copyItr->next = copyItr->next->next;
itr = itr->next;
copyItr = copyItr->next;
}
itr->next = NULL;
return new List(copyHead);
}
Complexity: O(n)
Nice Solution. It would be even better if you can explain how you came up with this approach.
ReplyDeleteI was thinking for the hashing but I realized that Linked List Node have the property "next" and I can use next instead of hashing.
Deletewat is random pointer
ReplyDeletestruct llist
{
int data;
struct llist *next;
struct llist *random;
}
or wat is random pointer
Hi Awadhesh,
DeleteRandom pointer is a pointer which can point to any node in the list. See the problem statement