Practice/Microsoft/Leetcode 138. Copy List with Random Pointer

Leetcode 138. Copy List with Random Pointer

CodingMust

Problem

You are given the head of a linked list where each node contains an additional pointer called random. This random pointer can point to any node in the list or be null.

Your task is to create a deep copy of this linked list. The deep copy should consist entirely of new nodes, and the structure of the copied list must perfectly match the original, including all next and random pointer relationships.

Return the head of the cloned linked list.

Requirements

1. Create completely new node objects (not references to original nodes)
2. Preserve all next pointer relationships from the original list
3. Preserve all random pointer relationships from the original list
4. The original list must remain unmodified
5. Handle cases where random pointers are null, point to themselves, or point to any other node

Constraints

• The number of nodes in the list is in the range [0, 1000]
• -10000 <= Node.val <= 10000
• The random pointer may point to any node in the list or be null
• Your solution should aim for O(n) time complexity and ideally O(1) extra space (excluding the output)

Examples

Example 1:

Input: head = [[7,null],[13,0],[11,1]] Output: [[7,null],[13,0],[11,1]] Explanation: Node 0: val=7, next=Node1, random=null Node 1: val=13, next=Node2, random=Node0 Node 2: val=11, next=null, random=Node1 The cloned list maintains these exact relationships with new node objects.

Example 2:

Input: head = [[1,1],[2,0]] Output: [[1,1],[2,0]] Explanation: Node 0: val=1, next=Node1, random=Node1 Node 1: val=2, next=null, random=Node0 The random pointers create a circular reference pattern.

Example 3:

Input: head = [] Output: [] Explanation: Empty input returns empty output.