Deep-Copy a Linked List with Random Pointers

Problem Statement

You are given the head of a singly linked list where each node contains an integer val, a next pointer pointing to the next node in the chain, and a random pointer which could point to any node in the list or None.

Construct a deep copy of the list reachable from head by following next pointers. The deep copy should consist of exactly n brand-new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointers of the copied nodes should point to new nodes in the copied list such that the original relationships are preserved. If a random pointer in the original list points to None, the copied node's random pointer must also be None.

None of the pointers in the new list should point to nodes in the original list, and the original list must not be permanently altered.

Return the head of the copied linked list.

Node Definition

class Node:
    def __init__(self, val: int, next: 'Node' = None, random: 'Node' = None):
        self.val = val
        self.next = next
        self.random = random

Function Signature

def copy_random_list(head: Optional[Node]) -> Optional[Node]:
    pass

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]]
Explanation:
- Node 0 (val = 7): next -> Node 1, random -> None
- Node 1 (val = 13): next -> Node 2, random -> Node 0
- Node 2 (val = 11): next -> Node 3, random -> Node 4
- Node 3 (val = 10): next -> Node 4, random -> Node 2
- Node 4 (val = 1): next -> None, random -> Node 0
All nodes in the output are newly allocated.

Example 2:

Input: head = [[1, 1], [2, 1]]
Output: [[1, 1], [2, 1]]
Explanation:
- Node 0 has val = 1, next -> Node 1, random -> Node 0 (self-loop).
- Node 1 has val = 2, next -> None, random -> Node 0.

Constraints

• The number of nodes in the list is in the range [0, 10^4].
• -10^4 <= Node.val <= 10^4
• Node.random is None or points to some node in the list reachable from head via next.

Edge Cases

• Empty list (head = None).
• Single node with random = None or self-referential random.
• All random pointers pointing to the same node.