Clone List with Random Pointer

Back to home
Logicmojo - Updated Aug 28, 2021



Problem Statement: Clone List with Random Pointer

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

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state.


Example:

head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]


We have presented two approaches to solve the problem:

 • Using - Extra Space
 • Without using - Extra Space


Approach 1: Using extra space


An intuitive solution is to keep a hash table for each node in the list, via which we just need to iterate the list in 2 rounds respectively to create nodes and assign the values for their random pointers. As a result, the space complexity of this solution is O(N), although with a linear time complexity.

C++ Implementation:

class Solution {
            public:
                Node* copyRandomList(Node* head) {
                    map<Node*, Node*> m;
                    int i=0;
                    Node* ptr = head;
                    while (ptr) {
                        m[ptr] =new Node(ptr->val);
                        ptr = ptr->next;
                    }
                    ptr = head;
                    while (ptr) {
                        m[ptr]->next = m[ptr->next];
                        m[ptr]->random = m[ptr->random];
                        ptr = ptr->next;
                    }
                    return m[head];
                }
            };
            


Python Implementation:

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.random = None

def copyRandomList(head):
    if head is None: return None
    mapping = {}
    cur = head
    while cur:
        mapping[cur] = Node(cur.val)
        cur = cur.next
    cur = head
    while cur:
        if cur.next:
            mapping[cur].next = mapping[cur.next]
        if cur.random:
            mapping[cur].random = mapping[cur.random]
        cur = cur.next
    return mapping[head]
def display(head):
    while head:
        if head.random:
            print(head.val, f"({head.random.val})", end=' -> ')
        else:
            print(head.val, "(X)", end=' -> ')
        head = head.next
    print("X")

if __name__=='__main__':
    head = Node(3)
    head.next = Node(4)
    head.next.next = Node(5)
    head.next.next.next = Node(6)
    head.next.next.next.next = Node(7)

    head.random = head.next
    head.next.random = head
    head.next.next.random = head.next.next.next.next
    head.next.next.next.random = head.next.next.next.next
    head.next.next.next.next.random = head.next
    
    display(head)
    head1 = copyRandomList(head)
    display(head1)

Time Complexity: O(N)

Space Complexity: O(N)



Approach 2: Without using Extra space


As an optimised solution, we could reduce the space complexity into constant. The idea is to associate the original node with its copy node in a single linked list. In this way, we don't need extra space to keep track of the new nodes.


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.


C++ Implementation:

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node * head_cp = nullptr, * cur = head, * cur_cp = nullptr;
        if (head == nullptr)
            return nullptr;
        while (cur != nullptr)
        {
            cur_cp = new Node(cur->val, cur->next, nullptr);
            cur->next = cur_cp;
            cur = cur_cp->next;
        }
        cur = head;
        while (cur != nullptr)
        {
            cur_cp = cur->next;
            if (cur->random)
                cur_cp->random = cur->random->next;
            cur = cur_cp ->next;
        }
        cur = head;
        head_cp = head->next;
        while (cur != nullptr)
        {
            cur_cp = cur->next;
            cur->next = cur_cp->next;
            cur = cur->next;
            if (cur)
                cur_cp->next = cur->next;
        }
        return head_cp;
    }
};


Python Implementation:

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.random = None

def copyRandomList(head):
    if not head: return head
#     Creating clone of nodes 1-2-3 = 1-1-2-2-3-3
    ptr = head
    while ptr:
        copy = Node(ptr.val)
        copy.next = ptr.next
        ptr.next = copy
        ptr = copy.next
#     assigning random pointer to the copy node
    ptr = head
    while ptr:
        copy = ptr.next
        copy.random = ptr.random.next if ptr.random else None
        ptr = copy.next
#     detaching the copy node and return newhead
    ptr = head
    newhead = head.next
    while ptr:
        copy = ptr.next
        ptr.next = copy.next
        copy.next = copy.next.next if copy.next else None
        ptr = ptr.next
    return newhead
def display(head):
    while head:
        if head.random:
            print(head.val, f"({head.random.val})", end=' -> ')
        else:
            print(head.val, "(X)", end=' -> ')
        head = head.next
    print("X")

if __name__=='__main__':
    head = Node(3)
    head.next = Node(4)
    head.next.next = Node(5)
    head.next.next.next = Node(6)
    head.next.next.next.next = Node(7)

    head.random = head.next.next.next
    head.next.random = head
    head.next.next.random = head.next.next.next.next
    head.next.next.next.random = head.next.next.next.next
    head.next.next.next.next.random = head.next
    
    display(head)
    head1 = copyRandomList(head)
    display(head1)

Time Complexity: O(N)

Space Complexity: O(1)


With this article at Logicmojo, you must have the complete idea of solving Clone a linked list with random pointer problem.