Clone a Linked List with random and next pointer

Dec 18, 2024 • 5 mins read

Problem Overview

The problem "Copy List with Random Pointer" from LeetCode is a classic example of deep copying a data structure with linked lists that have complex interconnections. In this problem, you're given a linked list where each node contains an extra pointer called a "random" pointer, which can point to any node in the list or be null. The goal is to make a deep copy of this linked list.

This problem tests your understanding of linked lists and requires an efficient approach to handle additional pointers that present a challenge beyond the typical single-pointer structure of a linked list.

Understanding the Problem

The linked list in question consists of nodes with two pointers: next — a standard pointer that points to the next node in the list, and random — a pointer that can point to any node in the list or null. Each node in the list has a unique label or value. The task is to produce a copy of the list with an identical structure and contents, but completely independent nodes.

Example

Consider the list representation:

The list looks something like this:

1 -> 2 -> 3 -> None
|    |    |
v    v    v
3    1   None

In this case:

Node 1's random pointer points to Node 3.
Node 2's random pointer points to Node 1.
Node 3's random pointer points to None.

The copied structure should exactly mimic the connections of the original structure but should be composed of all new nodes with their individual pointers.

Key DSA Concepts and Theory

Linked Lists

A linked list is a linear data structure consisting of nodes. Each node contains data and a pointer to the next node in the sequence. In this problem, each node also has an additional random pointer, making it a more complex variation of the standard singly linked list.

Deep Copy

A deep copy of an object refers to the creation of a copy that is entirely independent of the original. Modifications to the deep copy do not affect the original object and vice versa. This is critical in preserving the integrity of data shared between complex data structures.

HashMap (or Dictionary in certain languages)

A HashMap is used here to keep track of already copied nodes. By mapping nodes of the original list to the nodes of the copied list, you ensure that each node is copied only once and the random pointers can be correctly assigned.

Solution Approach

Step-by-step Explanation

The solution uses a combination of iteration and a HashMap to maintain references between the original nodes and their copies.

Iterate through the Original List:
- Traverse each node and create a new copy for each node. Use a HashMap to record the mapping between the original nodes and their respective copies.
- During this traversal, only the next pointers of the new nodes are assigned.
Assign Random Pointers:
- Traverse the original list a second time. For each node, use the HashMap to find the copied node, and set its random pointer using the mapping established in the HashMap.
Return the Head of the Copied List:
- The new head is the copied node that corresponds to the original head.

C++ Implementation

// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;
    
    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if (!head) return NULL;
        
        // HashMap to store the mapping from original nodes to their copies
        unordered_map<Node*, Node*> nodeMap;
        
        // First traversal: make a copy of all nodes and fill nodeMap
        Node* current = head;
        while (current) {
            nodeMap[current] = new Node(current->val);
            current = current->next;
        }
        
        // Second traversal: assign next and random pointers
        current = head;
        while (current) {
            nodeMap[current]->next = nodeMap[current->next];
            nodeMap[current]->random = nodeMap[current->random];
            current = current->next;
        }
        
        return nodeMap[head];
    }
};

Java Implementation

// 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;
    }
}

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

        // Map to hold original nodes to their copies
        Map<Node, Node> nodeMap = new HashMap<>();

        // First pass: Copy all nodes and fill the map
        Node current = head;
        while (current != null) {
            nodeMap.put(current, new Node(current.val));
            current = current.next;
        }

        // Second pass: Assign next and random pointers
        current = head;
        while (current != null) {
            nodeMap.get(current).next = nodeMap.get(current.next);
            nodeMap.get(current).random = nodeMap.get(current.random);
            current = current.next;
        }

        return nodeMap.get(head);
    }
}

Time and Space Complexity Analysis

Time Complexity: O(N), where N is the number of nodes in the linked list. The algorithm makes two passes over the list, so the time complexity is linear with respect to the size of the list.
Space Complexity: O(N), due to the extra space used by the HashMap to store the mapping from the original nodes to the copied nodes.

Common Mistakes to Avoid

Failing to handle cases where either the list or the random pointers are initially null.
Incorrectly assigning the random pointers, not using the HashMap correctly.

Additional Resources and References

By following this structured approach and utilizing HashMap for node mapping, solving the "Copy List with Random Pointer" problem becomes straightforward. Understanding these concepts sets a foundation for tackling more complex linked list problems involving additional pointer dimensions.

Terms & Conditions Privacy Policy Refund Policy