Create a deep copy of a linked list where each node has both a next pointer and a random pointer.
You are given the head of a linked list in which each node contains two references:
next points to the next node in the listrandom points to any node in the list or to nullConstruct a deep copy of the list. The copied list must contain new nodes with the same values and the same next/random relationships as the original list, but none of the new nodes may reuse nodes from the input list.
Return the head of the copied list.
A deep copy means every node in the new list is a newly created node, even if two nodes in the original list point to the same random target.
next reference, and a random reference.random may point to any node in the list or be null.Return the head node of a new linked list that is a deep copy of the original structure.
random pointers may form arbitrary connections, including self-references.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
The copied list has the same node values and pointer structure, but all nodes are newly created.
Example 2
Input
head = [[1,1],[2,1]]
Output
[[1,1],[2,1]]
Explanation
The first node's random pointer refers to itself, and the second node's random pointer refers to the first node. The clone must preserve these relationships.
Premium problem context
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.