Clone List with Random Pointer Editorial

Practice Problem Link: Clone List With Random Pointer

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given a linked list L₁ of length n. Each node contains an additional random pointer which could point to any of the nodes in the list, or null.

You need to create a deep copy of this list with n newly created nodes. This will create a new linked list L₂. All nodes of L₂ will have the same value as the corresponding node in L₁. The next and random pointers will point to nodes in L₂ rather than L₁.

Return the head of L₂.

Approach

• Traverse the given linked list and for every node create its copy and insert it just after the original node in the linked list.
• Now again traverse the modified list to assign the random pointer of each copy node. This can be done as currNode->next->random = currNode->random->next.
• This method works because currNode->next points to the copy node of the original node and currNode->random->next points to the copy node of the random pointer of the original node.
• Now traverse the list for the third time and extract the copied nodes from it to make a copy of the given linked list.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(1)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
    public:
    int data;
    ListNode *next;
    ListNode* random;
    ListNode (int data) {
        this->data = data;
        this->next = NULL;
        this->random = NULL;
    }
};
*/

ListNode* cloneTheLinkedList (ListNode* head) {
    ListNode* currNode = head;
	while (currNode != NULL) {
		ListNode* copyNode = new ListNode(currNode->data);
		copyNode->next = currNode->next;
		currNode->next = copyNode;
		currNode = currNode->next->next;	
	}
	currNode = head;
	while (currNode != NULL) {
		if (currNode->random != NULL) {
			currNode->next->random = currNode->random->next;
		}
		currNode = currNode->next->next;
	}
	head = head->next;
	currNode = head;
	while (currNode->next != NULL) {
		currNode->next = currNode->next->next;
		currNode = currNode->next;
	}
	return head;
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;
    ListNode random;

	ListNode (int data) {
        this.data = data;
        this.next = null;
        this.random = null;
    }
}
**/
class Solution {
	ListNode cloneTheLinkedList(ListNode head) {
		ListNode currNode = head;
		while (currNode != null) {
			ListNode copyNode = new ListNode(currNode.data);
			copyNode.next = currNode.next;
			currNode.next = copyNode;
			currNode = currNode.next.next;	
		}
		currNode = head;
		while (currNode != null) {
			if (currNode.random != null) {
				currNode.next.random = currNode.random.next;
			}
			currNode = currNode.next.next;
		}
		head = head.next;
		currNode = head;
		while (currNode.next != null) {
			currNode.next = currNode.next.next;
			currNode = currNode.next;
		}
		return head;
	}
}

Another Approach

• Traverse the given linked list and for every node create its copy and store the original and copy node in a hashmap.
• Since all the copy nodes are now present in the hashmap, simply traverse the linked list again and for every value in the hashmap assign the next and random pointers of the copy nodes using the next and random pointers of the original nodes.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

/* This is the ListNode class definition

class ListNode {
    public:
    int data;
    ListNode *next;
    ListNode* random;
    ListNode (int data) {
        this->data = data;
        this->next = NULL;
        this->random = NULL;
    }
};
*/

ListNode* cloneTheLinkedList (ListNode* head) {
    unordered_map<ListNode*, ListNode*> copyNodes;
	ListNode* currNode = head;
	while(currNode != NULL) {
		copyNodes[currNode] = new ListNode(currNode->data);
		currNode = currNode->next;
	}
	currNode = head;
	while(currNode != NULL) {
		copyNodes[currNode]->next = copyNodes[currNode->next];
		copyNodes[currNode]->random = copyNodes[currNode->random];
		currNode = currNode->next;
	}
	return copyNodes[head];
}

Java

/** This is the ListNode class definition

class ListNode {
	int data;
	ListNode next;
    ListNode random;

	ListNode (int data) {
        this.data = data;
        this.next = null;
        this.random = null;
    }
}
**/
class Solution {
	ListNode cloneTheLinkedList(ListNode head) {
		HashMap<ListNode, ListNode> copyNodes = new HashMap<ListNode, ListNode>();
		ListNode currNode = head;
		while(currNode != null) {
			copyNodes.put(currNode, new ListNode(currNode.data));
			currNode = currNode.next;
		}
		currNode = head;
		while(currNode != null) {
			copyNodes.get(currNode).next = copyNodes.get(currNode.next);
			copyNodes.get(currNode).random = copyNodes.get(currNode.random);
			currNode = currNode.next;
		}
		return copyNodes.get(head);
	}
}