138. Copy List with Random Pointer

Description

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.

Constraints

• -10000 <= Node.val <= 10000

• Node.random is null or pointing to a node in the linked list.

• Number of Nodes will not exceed 1000.

Approach

Links

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

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.

Solutions

Node

// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}

Solution 1

/**
 * Time complexity : O(N) where N is the number of nodes in the linked list.
 * Space complexity : O(N). If we look closely, we have the recursion stack 
 *    and we also have the space complexity to keep track of nodes already 
 *    cloned i.e. using the visited dictionary. But asymptotically, 
 *    the complexity is O(N).
 */

class Solution {
    public Node copyRandomList(Node head) {
        Map<Node, Node> nodes = new HashMap();
        return helper(head, nodes);
    }
    
    private Node helper(Node node, Map<Node, Node> nodes) {
        if(node == null) return null;
        
        if(nodes.containsKey(node)) {
            return nodes.get(node);
        }
        
        Node newNode = new Node(node.val);
        nodes.put(node, newNode);
        
        newNode.next = helper(node.next, nodes);
        newNode.random = helper(node.random, nodes);
        
        return newNode;
    }
}

Follow up