138. 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.

Thoughts: O(n) time complexity, O(n) space Complexity

1. Make deep copy of each node by tying right after each node

2. Copy random pointer

3. Extract the copy list and restore the original list

Code: without dummy node (copyHead at head->next)

/**
* Definition for singly-linked list with a random pointer.
* struct RandomListNode {
* int label;
* RandomListNode *next, *random;
* RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
* };
*/
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        if(!head) return nullptr;
        RandomListNode* cur = head, *next;

        // copying each node right after the current node
        while(cur){
            next = cur->next;
            RandomListNode* copyNode = new RandomListNode(cur->label);
            cur->next = copyNode;
            copyNode -> next = next;
            cur = next;
        }

        // copying random pointer
        cur = head;

        while(cur){
            next = cur -> next -> next;
            if(cur->random)
            cur->next->random = cur->random->next; // cur->random->next is the copy of corresponding random node
            // for the current node in original linked list

            cur = next;
        }

        // extract copy list and restore original list
        cur = head;
        RandomListNode *copyHead = head->next, *copyIter = copyHead;

        while(cur){
            next = cur -> next -> next;
            if(next) copyIter->next = next -> next;

            copyIter = copyIter->next;
            cur->next = next;
            cur = next;
        }

        return copyHead;
    }
};

Code: with dummy node (copyHead->next is the head->next): This one does not have to check null

T: O(n); S: O(1)

The algorithm is composed of the follow three steps which are also 3 iteration rounds.

1. Iterate the original list and duplicate each node. The duplicate of each node follows its original immediately.

2. Iterate the new list and assign the random pointer for each duplicated node.

3. Restore the original list and extract the duplicated nodes.

/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode* cur = head, *next;
        // copying each node right after the current node 
        while(cur){
            next = cur->next;
            RandomListNode* copyNode = new RandomListNode(cur->label);
            cur->next = copyNode;
            copyNode -> next = next;
            cur = next;
        }

        // copying random pointer
        cur = head;
        while(cur){
            next = cur -> next -> next;
            if(cur->random)
                cur->next->random = cur->random->next; // cur->random->next is the copy of corresponding random node 
                                                        // for the current node in original linked list

            cur = next;
        }

        // extract copy list and restore original list
        cur = head;
        RandomListNode * dummyHead = new RandomListNode(0), *copyIter = dummyHead;
        while(cur){
            next = cur -> next -> next;
            copyIter->next = cur -> next;
            copyIter = copyIter->next;

            cur->next = next;
            cur = next;
        }

        return dummyHead->next;
    }
};

Code: Copy everything from the dictionary. Space O(n)

# Definition for singly-linked list with a random pointer.
# class RandomListNode(object):
#     def __init__(self, x):
#         self.label = x
#         self.next = None
#         self.random = None

class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: RandomListNode
        :rtype: RandomListNode
        """
        # set the default value to be changed later using collections.defaultdict ()
        mapping = collections.defaultdict(lambda: RandomListNode(0))
        # set the None identity mapping 
        mapping[None] = None

        cur = head

        while cur:
            mapping[cur].label = cur.label
            mapping[cur].next = mapping[cur.next]
            mapping[cur].random = mapping[cur.random]
            cur = cur.next

        return mapping[head]

Special Thanks to liaison's solution for the reference