LeetCode 138: Copy List with Random Pointer Solution in Python Explained

Problem Statement

In LeetCode 138, you’re given the head of a linked list where each node contains an integer value, a next pointer to the next node (or null), and a random pointer to any node in the list (or null). Your task is to return a deep copy of the list, duplicating all nodes and pointers. This differs from array problems like LeetCode 137: Single Number II, focusing on linked list manipulation rather than singleton detection.

Constraints

• Number of nodes: 0 <= n <= 1000
• Node values: -10^4 <= Node.val <= 10^4
• random pointer can be any node or null

Example

Let’s see some cases:

Copy codeInput: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
      7 -> 13 -> 11 -> 10 -> 1
      |     |     |     |     |
     null  7    1    11    7
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Explanation: Deep copy with same structure and pointers.
<ul>
<li>7.random = null</li>
<li>13.random = copied 7</li>
<li>11.random = copied 1</li>
<li>10.random = copied 11</li>
<li>1.random = copied 7</li>
</ul>

Copy codeInput: head = [[1,1],[2,1]]
      1 -> 2
      |    |
      2    1
Output: [[1,1],[2,1]]
Explanation: Copied 1->2, 1.random = copied 2, 2.random = copied 1.

Copy codeInput: head = []
Output: null
Explanation: Empty list, return null.

These examples show we’re duplicating a list with random pointers.

Understanding the Problem

How do you solve LeetCode 138: Copy List with Random Pointer in Python? Take head = [[7,null],[13,0],[11,4],[10,2],[1,0]]. We need a deep copy—duplicate each node (7->13->11->10->1), set next pointers, and adjust random pointers (e.g., 13.random to copied 7). The random pointers complicate a simple copy, as we can’t directly reference new nodes yet. This isn’t a path sum problem like LeetCode 113: Path Sum II; it’s about linked list cloning. We’ll use: 1. Interweaving with Three Passes: O(n) time, O(1) space—our best solution. 2. Hash Map with Single Pass: O(n) time, O(n) space—an alternative.

Let’s dive into the best solution.

Best Solution: Interweaving with Three Passes Approach

Explanation

Interweaving with Three Passes creates a deep copy in three steps: 1. Interweave copied nodes between originals (e.g., 1->1'->2->2'). 2. Set random pointers using interleaved structure (e.g., 1'.random = 1.random.next). 3. Separate the copied list from the original.

This is the best solution due to its O(n) time complexity, O(1) space usage (no extra data structures), and clever use of the list itself to manage pointers, making it both efficient and space-optimal.

For [7,null],[13,0],[11,4],[10,2],[1,0]:

• Interweave: 7->7'->13->13'->11->11'->10->10'->1->1'.
• Set random: 7'.random = null, 13'.random = 7', etc.
• Separate: 7'->13'->11'->10'->1'.

Step-by-Step Example

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

Example 1: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]

Goal: Return copied list head.

• Step 1: Interweave:
• Original: 7->13->11->10->1.
• After: 7->7'->13->13'->11->11'->10->10'->1->1'.
• Each copied node (e.g., 7') follows its original (7).
• Step 2: Set Random Pointers:
• 7.random = null, 7'.random = null.
• 13.random = 7, 13'.random = 7' (13.random.next).
• 11.random = 1, 11'.random = 1'.
• 10.random = 11, 10'.random = 11'.
• 1.random = 7, 1'.random = 7'.
• Step 3: Separate:
• Original: 7->13->11->10->1.
• Copied: 7'->13'->11'->10'->1'.
• Finish: Return copied head (7').

Example 2: head = [[1,1],[2,1]]

Goal: Return copied list head.

• Interweave: 1->1'->2->2'.
• Random: 1'.random = 2', 2'.random = 1'.
• Separate: 1'->2'.
• Finish: Return 1'.

Example 3: head = []

Goal: Return null.

• Start: Null input, return null.
• Finish: Return null.

How the Code Works (Interweaving with Three Passes) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

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

def copyRandomList(head: 'Node') -> 'Node':
    # Line 1: Handle null input
    if not head:
        # If head is None (e.g., empty list), return None
        return None

    # Line 2: First Pass - Interweave copied nodes
    curr = head
    while curr:
        # curr = current original node (e.g., 7)
        copied = Node(curr.val)
        # Create copy (e.g., 7')
        copied.next = curr.next
        # Link copy to next original (e.g., 7'->13)
        curr.next = copied
        # Link original to copy (e.g., 7->7')
        curr = copied.next
        # Move to next original (e.g., 13)
    # Result: 7->7'->13->13'->...

    # Line 3: Second Pass - Set random pointers
    curr = head
    while curr:
        # curr = original node (e.g., 7)
        copied = curr.next
        # copied = interleaved copy (e.g., 7')
        if curr.random:
            # If original has random (e.g., 13.random=7)
            copied.random = curr.random.next
            # Set copy’s random (e.g., 13'.random=7')
        curr = copied.next
        # Move to next original (e.g., 13)
    # Random pointers set (e.g., 13'.random = 7')

    # Line 4: Third Pass - Separate lists
    dummy = Node(0)
    # Dummy head for copied list
    copied_curr = dummy
    # Pointer for building copied list (e.g., starts at dummy)
    curr = head
    # Pointer for original list (e.g., 7)
    while curr:
        # While original list remains (e.g., 7->7'->...)
        copied_curr.next = curr.next
        # Link copied list (e.g., dummy->7')
        copied_curr = copied_curr.next
        # Move copied pointer (e.g., 7')
        curr.next = copied_curr.next
        # Restore original next (e.g., 7->13)
        curr = curr.next
        # Move original pointer (e.g., 13)
    # Original: 7->13->..., Copied: 7'->13'->...

    # Line 5: Return copied list head
    return dummy.next
    # Returns copied list (e.g., 7')

This detailed breakdown clarifies how the interweaving approach efficiently copies the list.

Alternative: Hash Map with Single Pass Approach

Explanation

Hash Map with Single Pass uses a dictionary to map original nodes to their copies, creating all nodes in one pass, then setting pointers in a second pass. It’s a practical alternative, straightforward but uses O(n) space, less optimal than interweaving for space constraints.

For [7,null],[13,0],[11,4]:

• Map: {7:7', 13:13', 11:11'}.
• Set pointers: 13'.random = 7', 11'.random = 11'.

Step-by-Step Example (Alternative)

For [7,null],[13,0],[11,4]:

• Step 1: node_map = {7:7', 13:13', 11:11'}.
• Step 2:
• 7'.next = 13', 7'.random = None.
• 13'.next = 11', 13'.random = 7'.
• 11'.next = None, 11'.random = 11'.
• Finish: Return 7'.

How the Code Works (Hash Map)

Copy codedef copyRandomListHash(head: 'Node') -> 'Node':
    if not head:
        return None
    node_map = {}
    curr = head
    while curr:
        node_map[curr] = Node(curr.val)
        curr = curr.next
    curr = head
    while curr:
        copied = node_map[curr]
        copied.next = node_map.get(curr.next)
        copied.random = node_map.get(curr.random)
        curr = curr.next
    return node_map[head]

Complexity

• Interweaving with Three Passes:
• Time: O(n) – three passes.
• Space: O(1) – no extra space.
• Hash Map with Single Pass:
• Time: O(n) – two passes.
• Space: O(n) – hash map.

Efficiency Notes

Interweaving with Three Passes is the best solution with O(n) time and O(1) space, meeting optimal constraints elegantly—Hash Map with Single Pass matches time complexity but uses O(n) space, making it simpler but less space-efficient.

Key Insights

• Interweaving: Uses list structure.
• Hash Map: Maps originals to copies.
• Random Pointers: Require careful linking.

Additional Example

For head = [1,null],[2,0]:

• Goal: Copied list.
• Interweaving: 1->1'->2->2', 2'.random = 1'.

Edge Cases

• Empty List: [] → null.
• Single Node: [1,null] → [1,null].
• All Random: [1,0],[2,0] → [1,0'],[2,0'].

Both solutions handle these well.

Final Thoughts

LeetCode 138: Copy List with Random Pointer in Python is a clever linked list challenge. The Interweaving with Three Passes solution excels with its efficiency and space usage, while Hash Map with Single Pass offers a clear approach. Want more? Try LeetCode 141: Linked List Cycle for list basics or LeetCode 136: Single Number for bitwise fun. Ready to practice? Solve LeetCode 138 on LeetCode with [[7,null],[13,0],[11,4],[10,2],[1,0]], aiming for a deep copy—test your skills now!