Create a deep copy of a linked list where each node has both a next pointer and a random pointer.
Problem
You are given the head of a linked list in which each node contains two references:
nextpoints to the next node in the listrandompoints to any node in the list or tonull
Construct 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.
Input Format
- The input is the head node of a singly linked list.
- Each node has an integer value, a
nextreference, and arandomreference. randommay point to any node in the list or benull.
Output Format
Return the head node of a new linked list that is a deep copy of the original structure.
Constraints
- The list may be empty.
randompointers may form arbitrary connections, including self-references.- The copied list must preserve both node values and pointer structure.
- Use newly allocated nodes only for the copied list.
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
Unlock deeper context for this problem
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.