Thursday, May 21, 2015

Flipkart Question: Clone a linked list with next and random pointer

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:
  1. Create the copy each node in the list and insert it between node and its next.
  2. Now copy the random pointer as follows:
    • node->next->random = node->random->next
  3. 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)

4 comments:

  1. Nice Solution. It would be even better if you can explain how you came up with this approach.

    ReplyDelete
    Replies
    1. I was thinking for the hashing but I realized that Linked List Node have the property "next" and I can use next instead of hashing.

      Delete
  2. wat is random pointer
    struct llist
    {
    int data;
    struct llist *next;
    struct llist *random;
    }
    or wat is random pointer

    ReplyDelete
    Replies
    1. Hi Awadhesh,
      Random pointer is a pointer which can point to any node in the list. See the problem statement

      Delete