Copy List with Random Pointer

Problem Statement

In this task, we have a unique data structure called a linked list where each node not only points to the next node in sequence via the next pointer, but also has an additional random pointer. This random pointer can link to any node within the list (or to none at all, i.e., null).

The challenge stems from needing to create a deep copy of this linked list. A deep copy involves generating entirely new nodes that replicate the value and the pattern of next and random connections of the original list. Unlike a shallow copy, where the copy might still contain references to original pieces, each node and linkage in a deep copy stands alone and independent of the original dataset.

This problem calls for precision in handling pointers, particularly ensuring that the new list's random pointers correlate directly with the new corresponding nodes, not the initial ones. Therefore, the outcome should maintain both the sequence (next pointers) and the random relationships, without retaining any references to the original list nodes.

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

Constraints

• 0 <= n <= 1000
• -104 <= Node.val <= 104
• Node.random is null or is pointing to some node in the linked list.

Approach and Intuition

To tackle the problem of creating a deep copy of a linked list with both next and random pointers, consider the following approach, drawn from the provided examples and constraints:

1. Iterative Relation Establishment with Mapping:

   • Initialize a hashmap to track and relate original nodes to their respective clones. This data structure will expedite access and prevent the recreation of already copied nodes.
   • Traverse the original linked list. For each node, create a clone and add it to the hashmap.
   • On this first pass, only establish the next pointers for the clones using the hashmap to prevent the lingering dependency on original nodes.
   • In a subsequent traversal, set up the random pointers for each cloned node. Use the hashmap to translate the random pointers from the original to the corresponding cloned nodes accurately.

2. Edge Cases Handling:

   • For lists of length n = 0, simply return null as there are no nodes to copy.
   • For the random pointer, ensure each cloned random pointer maps correctly even if the original pointer is null.

3. Efficiency Considerations:

   • Given the constraint (0 <= n <= 1000), creating a structure of one hashmap and two full list traversals should remain computationally reasonable.
   • Directly read and establish connections in two separate passes to avoid complications or corruptions, such as prematurely linking clones or inadvertently contiguous assignments.

This approach, by accurately using an auxiliary hashmap and ensuring comprehensiveness in node linkage assignment, encapsulates an efficient and error-resistant method to achieve the deep copy of a complex linked list.

Solutions

class Solution {
public:
    Node* cloneListWithRandomPointer(Node* original_head) {
        if (!original_head) {
            return nullptr;
        }
    
        Node* current = original_head;
        while (current != nullptr) {
            Node* clone = new Node(current->val, nullptr, nullptr);
            clone->next = current->next;
            current->next = clone;
            current = clone->next;
        }
    
        current = original_head;
        while (current != nullptr) {
            current->next->random = current->random ? current->random->next : nullptr;
            current = current->next->next;
        }
    
        Node* old_list = original_head;
        Node* new_list = original_head->next;
        Node* new_head = original_head->next;
        while (old_list != nullptr) {
            old_list->next = old_list->next->next;
            new_list->next = new_list->next ? new_list->next->next : nullptr;
            old_list = old_list->next;
            new_list = new_list->next;
        }
    
        return new_head;
    }
};