Copy List With Random Pointer

                                            
import java.util.HashMap;
import java.util.Map;

/*
// 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<Node, Node> map = new HashMap<>();
        Node curr = head;

        while (curr != null) {
            map.put(curr, new Node(curr.val));
            curr = curr.next;
        }

        curr = head;
        while (curr != null) {
            map.get(curr).next = map.get(curr.next);
            map.get(curr).random = map.get(curr.random);
            curr = curr.next;
        }

        return map.get(head);
    }
}

                                            
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */

struct Node* copyRandomList(struct Node* head) {
    if (head == NULL) {
        return NULL;
    }
    
    struct Node* curr = head;
    struct Node* next;
    
    // Create a copy of each node in the original list and insert it next to the original node
    while (curr != NULL) {
        next = curr->next;
        
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = curr->val;
        copy->next = next;
        copy->random = NULL;
        
        curr->next = copy;
        curr = next;
    }
    
    // Assign random pointers for the copy nodes
    curr = head;
    while (curr != NULL) {
        next = curr->next->next;
        if (curr->random != NULL) {
            curr->next->random = curr->random->next;
        }
        curr = next;
    }
    
    // Separate the original list and the copied list
    struct Node* original = head;
    struct Node* copy = head->next;
    struct Node* result = copy;
    
    while (original != NULL) {
        original->next = copy->next;
        original = original->next;
        if (original != NULL) {
            copy->next = original->next;
            copy = copy->next;
        }
    }
    
    return result;
}

                                            
const copyRandomList = function(head) {
    if (!head) return null;

    let map = new Map();
    let current = head;

    while (current) {
        map.set(current, new Node(current.val));
        current = current.next;
    }

    current = head;

    while (current) {
        map.get(current).next = map.get(current.next) || null;
        map.get(current).random = map.get(current.random) || null;
        current = current.next;
    }

    return map.get(head);
};

                                            
/**
 * Definition for Node.
 * class Node {
 *     val: number
 *     next: Node | null
 *     random: Node | null
 *     constructor(val?: number, next?: Node, random?: Node) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *         this.random = (random===undefined ? null : random)
 *     }
 * }
 */
function copyRandomList(head: Node | null): Node | null {
    if (!head) return null;
    
    const map = new Map();
    let curr = head;
    
    while (curr) {
        map.set(curr, new Node(curr.val));
        curr = curr.next;
    }
    
    curr = head;
    while (curr) {
        map.get(curr).next = map.get(curr.next) || null;
        map.get(curr).random = map.get(curr.random) || null;
        curr = curr.next;
    }
    
    return map.get(head);
};

                                            
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

func copyRandomList(head *Node) *Node {
    if head == nil {
        return nil
    }

    visited := make(map[*Node]*Node)

    // Create new nodes without setting random pointer
    current := head
    for current != nil {
        visited[current] = &Node{Val: current.Val}
        current = current.Next
    }

    // Set the random pointers
    current = head
    for current != nil {
        visited[current].Next = visited[current.Next]
        visited[current].Random = visited[current.Random]
        current = current.Next
    }

    // Return the head of the new list
    return visited[head]
}

                                            
# Definition for Node.
# class Node
#     attr_accessor :val, :next, :random
#     def initialize(val = 0)
#         @val = val
#         @next = nil
#         @random = nil
#     end

# @param {Node} head
# @return {Node}
def copyRandomList(head)
  return nil if head.nil?
  
  node_mapping = {}
  
  current = head
  while current
    node_mapping[current] = Node.new(current.val)
    current = current.next
  end
  
  current = head
  while current
    node_mapping[current].next = node_mapping[current.next]
    node_mapping[current].random = node_mapping[current.random]
    current = current.next
  end
  
  return node_mapping[head]
end

To solve this coding challenge, we need to create a deep copy of a linked list where each node has a next pointer and a random pointer. This involves creating new nodes such that both the next and random pointers in the copied list point to new nodes in the copied list, maintaining the same structure as the original list. Below is a detailed explanation of how we can achieve this along with pseudocode.

Explanation

Initialization :

We need to handle the case where the input list is empty (
n == 0

). If the list is empty, we immediately return
null

.
For all non-empty lists, we will use a map (or dictionary) to store the mapping between the original nodes and their corresponding new nodes. This allows us to efficiently create a deep copy and set the appropriate pointers.

First Pass :

Traverse the original list and create a new node for each original node. During this traversal, populate the map with the original nodes as keys and the newly created nodes as the corresponding values.

Second Pass :

Traverse the original list again, this time setting the
next

and
random

pointers of the newly created nodes using the map. This ensures that the
next

and
random

pointers in the copied list point to the appropriate new nodes, maintaining the original list structure.

Return the head :

Finally, return the new head that is stored as the value in the map corresponding to the original head node.

This process ensures that we accurately copy both the

next

and

random

pointers for each node, creating a deep copy of the entire list.

Pseudocode

                                            
# Function to copy the list with random pointer
function copyRandomList(head):
# Check if the input list is empty
if head is null:
return null

# Initialize a map to keep track of original to new node mapping
node_map = map()

# Pointer to the current node in the original list
original_node = head

# First pass to create new nodes and populate the map
while original_node is not null:
# Create a new node with the same value as the original node
new_node = new Node(original_node.value)

# Add the original and new node pair to the map
node_map.set(original_node, new_node)

# Move to the next node in the original list
original_node = original_node.next

# Reset the pointer to the head of the original list for the second pass
original_node = head

# Second pass to set the next and random pointers in the new list
while original_node is not null:
# Get the corresponding new node from the map
new_node = node_map.get(original_node)

# Set the next pointer for the new node
new_node.next = node_map.get(original_node.next) if original_node.next is not null else null

# Set the random pointer for the new node
new_node.random = node_map.get(original_node.random) if original_node.random is not null else null

# Move to the next node in the original list
original_node = original_node.next

# Return the new head corresponding to the original head
return node_map.get(head)

Detailed Steps in Pseudocode

Check if the input list is empty :

If
head

is
null

, immediately return
null

.

Initialize the map :

Create an empty map called
node_map

to hold the mapping between original nodes and their corresponding new nodes.

First Pass: Create Nodes :

Initialize
original_node

pointer to
head

.
Traverse the list using a
while

loop:

For each node
original_node

, create a
new_node

with the same
value

.
Insert
original_node

and
new_node

into
node_map

.
Move
original_node

to its next node using
original_node.next

.

Second Pass: Set Pointers :

Reset
original_node

to
head

again.
Traverse the list using a
while

loop:

For each node
original_node

, get
new_node

from
node_map

.
Set
new_node.next

to the node mapped from
original_node.next

or
null

if
original_node.next

is
null

.
Set
new_node.random

to the node mapped from
original_node.random

or
null

if
original_node.random

is
null

.
Move
original_node

to its next node.

Return the new head :

Return
node_map.get(head)

which gives the new head corresponding to the original head.

This method ensures a correct deep copy of the list, including maintaining the correct

random

pointers.