**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:**

- 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