Copy List with Random Pointer medium

Problem Statement

A linked list of length n is given such that each node contains an integer val and a pointer random to the node at a random index or null. Construct a deep copy of the given linked list. The chain must be deep; each node in the new chain must be a distinct object, not the same as any node in the original list.

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]]

Steps

The problem requires creating a deep copy of a linked list with random pointers. A naive approach would lead to infinite loops. We can solve this using a hashmap to track visited nodes and their corresponding copies. The algorithm proceeds as follows:

1. Iterate through the original list: Create a new node for each node in the original list. Store the mapping between original nodes and their copies in a hashmap (Dictionary in C#).
2. Handle random pointers: For each new node, set its random pointer based on the random pointer of the corresponding original node. Use the hashmap to find the copied node corresponding to the original node pointed to by random.
3. Return the head of the copied list: After iterating through all nodes, return the head of the newly created list.

Explanation

The hashmap (Dictionary) is crucial for avoiding cycles and ensuring a deep copy. It allows us to quickly look up the copy of a node when setting the random pointers. The algorithm ensures each node in the copied list is a distinct object, fulfilling the requirements of the problem.

Code

using System;
using System.Collections.Generic;

public class Node {
    public int val;
    public Node next;
    public Node random;

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

public class Solution {
    public Node CopyRandomList(Node head) {
        if (head == null) return null;

        Dictionary<Node, Node> visited = new Dictionary<Node, Node>(); // Map original nodes to their copies

        Node oldNode = head;
        Node newNode = new Node(oldNode.val); // Create the first node of the copied list
        visited.Add(oldNode, newNode); // Add the mapping to the hashmap

        while (oldNode != null) {
            //Handle next pointers
            if (oldNode.next != null && !visited.ContainsKey(oldNode.next)) {
                newNode.next = new Node(oldNode.next.val);
                visited.Add(oldNode.next, newNode.next);
            } else if (oldNode.next != null) {
                newNode.next = visited[oldNode.next];
            }

            //Handle random pointers
            if (oldNode.random != null && !visited.ContainsKey(oldNode.random)) {
                newNode.random = new Node(oldNode.random.val);
                visited.Add(oldNode.random, newNode.random);
            } else if (oldNode.random != null) {
                newNode.random = visited[oldNode.random];
            }

            oldNode = oldNode.next;
            newNode = newNode.next;
        }
        return visited[head];
    }
}

Complexity

• Time Complexity: O(N), where N is the number of nodes in the linked list. We iterate through the list once to create copies and set pointers.
• Space Complexity: O(N), primarily due to the hashmap used to store the mapping between original and copied nodes. In the worst case, all nodes might be in the hashmap.