🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

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.
The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

val: an integer representing Node.val
random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Duplicate values allowed: MORE THAN ONE NODES COULD HAVE SAME VALUE.

Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]


Example 2:
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]


Example 3:
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]


Example 4:
Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Solution:

We will discuss two solutions here: one is time optimized and another one is space optimized, as discussed below:

#1. Solution with O(n) Time Complexity and O(n) Extra Space Complexity:

Just think if the problem were to do a deep copy of a linkedlist with only next pointer and no random pointer. Won't it be so easy ? You just iterate over the given linked list and for each node you create a node and point the next pointer of previous node to it. In the first part of our implementation we do exactly this, but along with that we also do a node to node mapping between the given linked list and the linked list we are creating so that we can come back and take care of the random pointers, which is done in the second part of the implementation. Look at the code below and it will become clear to you.
First part of code:

Map< Node, Node > nodeToNodeMapping = new HashMap<>();
Node newHead = new Node(head.val);
Node curr1 = head;
Node curr2 = newHead;
nodeToNodeMapping.put(head, newHead);
// Build the new linkedlist first, only with next pointer.
// We will bother about random pointer later
while (curr1.next != null) {
    Node nextNode1 = curr1.next;
    Node nextNode2 = new Node(nextNode1.val);
    curr2.next = nextNode2;
    nodeToNodeMapping.put(nextNode1, nextNode2);
    curr1 = curr1.next;
    curr2 = curr2.next;
}

Second part of code:

Node curr1 = head;
Node curr2 = newHead;
        
// let's get the random pointers done now
while (curr1 != null) {
    Node randomNode1 = curr1.random;
    if (randomNode1 != null) {
        curr2.random = nodeToNodeMapping.get(randomNode1);
    }
    curr1 = curr1.next;
    curr2 = curr2.next;
}

Complete Code:

Login to Access Content

#2. Solution with O(n²) Time Complexity and O(1) Space Complexity i.e No Extra Space:

Ask yourself: why did we have the keep map data structure in the above implementation ? We need the map because we know to which node the random pointer points to in the given linked list, but in the newly created linked list we do not know to which node we should point the random pointer. Also we cannot point to the random node at the same time as that of the new linked list creation, because the random node for a node may not have been created yet. Example, say 3rd node's random pointer points to 10th node. Since we are creating the node in sequential order when we are creating 3rd node at that only 1st and 2nd node are present (along with 3rd node) and 10th node has not been created yet. So we see we have room for improvement on space if we can tolerate to have worse time complexity. What we will do is: after we have created the new linked list with just the next pointers, we iterate over both the linked lists again and for each node in the given linked list we try to find out how far is the node from the head to which its random pointer points to. We use this information to correctly handle the random pointers for the newly created linked list. Take a loot at the code below and you would know what I mean.


Login to Access Content

Instructor: