Language Selection
Choose your preferred programming language
Showing: Python
Problem Statement
A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.
Construct a deep copy of the list. 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 new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.
Return the head of the copied linked list.
Input/Output Specifications
- Input: Head of a linked list with random pointers
- Output: Head of the deep copied linked list
- Constraints:
- 0 <= n <= 1000
- -10^4 <= Node.val <= 10^4
- Node.random is null or points to a node in the linked list
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]]
Example 2:
Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]
Solutions
Approach 1: Hash Map (Two Pass)
This approach uses a hash map to store the mapping between original and copied nodes, then sets up the random pointers in a second pass.
Algorithm:
- First pass: Create new nodes and store original->new mapping in hash map
- Second pass: Set up next and random pointers using the hash map
- Return the head of the copied list
Python:
def copyRandomList(head):
"""
Copy linked list with random pointers using hash map
Time: O(n)
Space: O(n)
"""
if not head:
return None
# First pass: create new nodes and store mapping
node_map = {}
current = head
while current:
node_map[current] = Node(current.val)
current = current.next
# Second pass: set up next and random pointers
current = head
while current:
copied_node = node_map[current]
# Set next pointer
if current.next:
copied_node.next = node_map[current.next]
# Set random pointer
if current.random:
copied_node.random = node_map[current.random]
current = current.next
return node_map[head]
Java:
class Solution {
/**
* Copy linked list with random pointers using hash map
* Time: O(n)
* Space: O(n)
*/
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// First pass: create new nodes and store mapping
Map<Node, Node> nodeMap = new HashMap<>();
Node current = head;
while (current != null) {
nodeMap.put(current, new Node(current.val));
current = current.next;
}
// Second pass: set up next and random pointers
current = head;
while (current != null) {
Node copiedNode = nodeMap.get(current);
// Set next pointer
if (current.next != null) {
copiedNode.next = nodeMap.get(current.next);
}
// Set random pointer
if (current.random != null) {
copiedNode.random = nodeMap.get(current.random);
}
current = current.next;
}
return nodeMap.get(head);
}
}
Go:
// copyRandomList - Copy linked list with random pointers using hash map
// Time: O(n)
// Space: O(n)
func copyRandomList(head *Node) *Node {
if head == nil {
return nil
}
// First pass: create new nodes and store mapping
nodeMap := make(map[*Node]*Node)
current := head
for current != nil {
nodeMap[current] = &Node{Val: current.Val}
current = current.Next
}
// Second pass: set up next and random pointers
current = head
for current != nil {
copiedNode := nodeMap[current]
// Set next pointer
if current.Next != nil {
copiedNode.Next = nodeMap[current.Next]
}
// Set random pointer
if current.Random != nil {
copiedNode.Random = nodeMap[current.Random]
}
current = current.Next
}
return nodeMap[head]
}
JavaScript:
/**
* Copy linked list with random pointers using hash map
* Time: O(n)
* Space: O(n)
*/
function copyRandomList(head) {
if (head === null) {
return null;
}
// First pass: create new nodes and store mapping
const nodeMap = new Map();
let current = head;
while (current !== null) {
nodeMap.set(current, new Node(current.val));
current = current.next;
}
// Second pass: set up next and random pointers
current = head;
while (current !== null) {
const copiedNode = nodeMap.get(current);
// Set next pointer
if (current.next !== null) {
copiedNode.next = nodeMap.get(current.next);
}
// Set random pointer
if (current.random !== null) {
copiedNode.random = nodeMap.get(current.random);
}
current = current.next;
}
return nodeMap.get(head);
}
C#:
public class Solution {
/// <summary>
/// Copy linked list with random pointers using hash map
/// Time: O(n)
/// Space: O(n)
/// </summary>
public Node CopyRandomList(Node head) {
if (head == null) {
return null;
}
// First pass: create new nodes and store mapping
Dictionary<Node, Node> nodeMap = new Dictionary<Node, Node>();
Node current = head;
while (current != null) {
nodeMap[current] = new Node(current.val);
current = current.next;
}
// Second pass: set up next and random pointers
current = head;
while (current != null) {
Node copiedNode = nodeMap[current];
// Set next pointer
if (current.next != null) {
copiedNode.next = nodeMap[current.next];
}
// Set random pointer
if (current.random != null) {
copiedNode.random = nodeMap[current.random];
}
current = current.next;
}
return nodeMap[head];
}
}
Approach 2: Interweaving (O(1) Space)
This approach interweaves the copied nodes with the original nodes, then separates them.
Algorithm:
- First pass: Create new nodes and insert them after each original node
- Second pass: Set up random pointers for copied nodes
- Third pass: Separate the interweaved lists
- Return the head of the copied list
Python:
def copyRandomListInterweaving(head):
"""
Copy linked list with random pointers using interweaving
Time: O(n)
Space: O(1)
"""
if not head:
return None
# First pass: create new nodes and insert after original nodes
current = head
while current:
new_node = Node(current.val)
new_node.next = current.next
current.next = new_node
current = new_node.next
# Second pass: set up random pointers
current = head
while current:
if current.random:
current.next.random = current.random.next
current = current.next.next
# Third pass: separate the lists
original_head = head
copied_head = head.next
current_original = original_head
current_copied = copied_head
while current_original:
current_original.next = current_original.next.next
if current_copied.next:
current_copied.next = current_copied.next.next
current_original = current_original.next
current_copied = current_copied.next
return copied_head
Java:
class Solution {
/**
* Copy linked list with random pointers using interweaving
* Time: O(n)
* Space: O(1)
*/
public Node copyRandomListInterweaving(Node head) {
if (head == null) {
return null;
}
// First pass: create new nodes and insert after original nodes
Node current = head;
while (current != null) {
Node newNode = new Node(current.val);
newNode.next = current.next;
current.next = newNode;
current = newNode.next;
}
// Second pass: set up random pointers
current = head;
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Third pass: separate the lists
Node originalHead = head;
Node copiedHead = head.next;
Node currentOriginal = originalHead;
Node currentCopied = copiedHead;
while (currentOriginal != null) {
currentOriginal.next = currentOriginal.next.next;
if (currentCopied.next != null) {
currentCopied.next = currentCopied.next.next;
}
currentOriginal = currentOriginal.next;
currentCopied = currentCopied.next;
}
return copiedHead;
}
}
Go:
// copyRandomListInterweaving - Copy linked list with random pointers using interweaving
// Time: O(n)
// Space: O(1)
func copyRandomListInterweaving(head *Node) *Node {
if head == nil {
return nil
}
// First pass: create new nodes and insert after original nodes
current := head
for current != nil {
newNode := &Node{Val: current.Val}
newNode.Next = current.Next
current.Next = newNode
current = newNode.Next
}
// Second pass: set up random pointers
current = head
for current != nil {
if current.Random != nil {
current.Next.Random = current.Random.Next
}
current = current.Next.Next
}
// Third pass: separate the lists
originalHead := head
copiedHead := head.Next
currentOriginal := originalHead
currentCopied := copiedHead
for currentOriginal != nil {
currentOriginal.Next = currentOriginal.Next.Next
if currentCopied.Next != nil {
currentCopied.Next = currentCopied.Next.Next
}
currentOriginal = currentOriginal.Next
currentCopied = currentCopied.Next
}
return copiedHead
}
JavaScript:
/**
* Copy linked list with random pointers using interweaving
* Time: O(n)
* Space: O(1)
*/
function copyRandomListInterweaving(head) {
if (head === null) {
return null;
}
// First pass: create new nodes and insert after original nodes
let current = head;
while (current !== null) {
const newNode = new Node(current.val);
newNode.next = current.next;
current.next = newNode;
current = newNode.next;
}
// Second pass: set up random pointers
current = head;
while (current !== null) {
if (current.random !== null) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Third pass: separate the lists
const originalHead = head;
const copiedHead = head.next;
let currentOriginal = originalHead;
let currentCopied = copiedHead;
while (currentOriginal !== null) {
currentOriginal.next = currentOriginal.next.next;
if (currentCopied.next !== null) {
currentCopied.next = currentCopied.next.next;
}
currentOriginal = currentOriginal.next;
currentCopied = currentCopied.next;
}
return copiedHead;
}
C#:
public class Solution {
/// <summary>
/// Copy linked list with random pointers using interweaving
/// Time: O(n)
/// Space: O(1)
/// </summary>
public Node CopyRandomListInterweaving(Node head) {
if (head == null) {
return null;
}
// First pass: create new nodes and insert after original nodes
Node current = head;
while (current != null) {
Node newNode = new Node(current.val);
newNode.next = current.next;
current.next = newNode;
current = newNode.next;
}
// Second pass: set up random pointers
current = head;
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Third pass: separate the lists
Node originalHead = head;
Node copiedHead = head.next;
Node currentOriginal = originalHead;
Node currentCopied = copiedHead;
while (currentOriginal != null) {
currentOriginal.next = currentOriginal.next.next;
if (currentCopied.next != null) {
currentCopied.next = currentCopied.next.next;
}
currentOriginal = currentOriginal.next;
currentCopied = currentCopied.next;
}
return copiedHead;
}
}
Key Insights
- Deep copy requirement: Create completely new nodes, not just references
- Random pointer complexity: Need to maintain relationships between original and copied nodes
- Hash map approach: Simple and intuitive, uses O(n) extra space
- Interweaving approach: Clever technique to achieve O(1) extra space
- Three-pass algorithm: Interweaving requires careful separation of lists
Edge Cases
- Empty list
- Single node list
- All random pointers are null
- Random pointers form cycles
- Random pointers point to the same node
Test Cases
# Test case 1: Normal case with random pointers
# Original: 7->13->11->10->1
# Random: 7->null, 13->7, 11->1, 10->11, 1->7
# Expected: Deep copy with same structure
# Test case 2: All random pointers null
# Original: 1->2->3
# Random: 1->null, 2->null, 3->null
# Expected: Deep copy with all random pointers null
# Test case 3: Random pointers form cycle
# Original: 1->2->3
# Random: 1->2, 2->3, 3->1
# Expected: Deep copy with same random structure
Follow-up Questions
- How would you handle cycles in the random pointers?
- Can you solve this with O(1) space and O(1) time?
- How would you validate that the copy is correct?
- What if the list is very large?
Common Mistakes
- Not creating deep copies (sharing references)
- Incorrectly setting up random pointers
- Not handling null random pointers
- Memory leaks when not properly managing pointers
- Off-by-one errors in the interweaving approach
- Not properly separating the interweaved lists