LeetCode Copy List with Random Pointer: O(N) Time and O(1) Space

Overview

LeetCode Copy List with Random Pointer: 1) Hash Table with O(N) extra space; 2) Insert the copied node between original nodes, O(1) extra space, linear time.

LeetCode Copy List with Random Pointer

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Two Approaches:  O(N) Time and O(1) Space

1) Use Hash table to do mapping between the original node and the copied node. There are two passes to scan the input linked list, during the first pass, we make the linked list and copy the next pointer and also insert <Origin Node Address, Copied Node Address> into the hash table. During the second pass, we make the random pointers correct in the copied linked list by setting the copied->random to the corresponding copied node:

Say the original node is A, and the copied node is A’, and A->random = F, correspondingly, F has a copied one F’ in the hash table, so for the copied linked list, we need to set A’->random to F’, and it could be accessed in O(1) time using the hash table, this is where the hash table come into play.

The following code implements this idea and is accepted by LeetCode OJ to pass this Copy List with Random Pointer:

class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            if (NULL == head)
                return NULL;
            unordered_map<RandomListNode *, RandomListNode *> hm;

            RandomListNode *copyHead = new RandomListNode(head->label);

            RandomListNode *p = head;
            RandomListNode *q = copyHead;
            hm[head] = copyHead;

            p = p->next;
            while (p) {
                q->next = new RandomListNode(p->label);
                hm[p] = q->next;
                p = p->next;
                q = q->next;
            }

            p = head, q = copyHead;
            while (p) {
                q->random = NULL;
                if (p->random) {
                    q->random = hm[p->random];
                }

                p = p->next;
                q = q->next;
            }
            return copyHead;
        }
};

While this approach is not difficult to come up with, this costs O(N) extra memory (excluding the final copied linked list) and could be further improved by using O(1) extra memory as the following.

2) There is a non-trivial approach which solves this problem with O(N) time and O(1) space (excluding the final copied linked list). I actually discussed this approach in Chinese in my old posts “Copy A Linked List With Next And Random Pointer“. Here is the detailed steps to take:

  1. Copy the original linked list and insert each copied node after the orginal one while before the original next node. Do not process the random pointers for now. So if the orignial linked list looks like this: A->B->C … -> Z->NULL, it would be like this: A->A’->B->B’->…Z->Z’->NULL
  2. Copy the random pointers by this statement: N->next->random = N->random->next, where N denotes any of the node in the original linked list. Here is the point: N->next is actually the copied node, by setting N->next->random we are trying the copy the correct corresponding node in the copied linked list,  you can easliry fighout out why it works by drawing yourself.
  3. Detach the two linked list into separete linked lists: A->B->…Z->NULL and A’->B’->…->Z’->NULL, A’->B’->…->Z’->NULL is just our result with the next pointers set correctly in setp 1 and the random pointers set correctly in step 2. Note that do not forget to set Z->next = NULL for the original linked list in this step for the correct results.

The following code implements this idea and is accepted by LeetCode OJ to pass this Copy List with Random Pointer as well:

class Solution {
    public:
        RandomListNode *copyRandomList(RandomListNode *head) {
            if (NULL == head)
                return NULL;

            RandomListNode *ptr = head;
            while (ptr) {
                RandomListNode *dup = new RandomListNode(ptr->label);
                dup->next = ptr->next;
                ptr->next = dup;
                ptr = dup->next;
            }

            ptr = head;
            while (ptr) {
                if (ptr->random)
                    ptr->next->random = ptr->random->next;
                else
                    ptr->next->random = NULL;
                ptr = ptr->next->next;
            }

            RandomListNode *newHead = head->next;
            RandomListNode *origin = head;
            RandomListNode *copied = head->next;

            while (copied->next) {
                origin->next = origin->next->next;
                copied->next = copied->next->next;

                origin = origin->next;
                copied = copied->next;
            }

            origin->next = NULL;

            return newHead;
        }
};

Note ptr->random could actually be NULL, so do not forget to check!

Summary

LeetCode Copy List with Random Pointer: 1) Hash Table with O(N) extra space; 2) Insert the copied node between original nodes, O(1) extra space, linear time.

Written on January 17, 2015