Framework Thinking - Neetcode 150 - Copy Linked List with Random Pointer

Here is solutions for Copy Linked List with Random Pointer

1. Understand the Problem

  • You are given a linked list where each node has:

    • next → points to the next node.

    • random → may point to any node in the list or None.

  • Your task: Create a deep copy of the linked list, meaning:

    • Duplicate every node.

    • Correctly assign next and random.

    • Return the head of the copied linked list.

    • DO NOT change the original list.

2. Clarify Constraints & Questions

  1. What if the list is empty?

-> Return None.

  1. Can random pointers point to nodes ahead or behind, including itself?

-> Yes.

  1. Can there be cycles via random pointers?

-> Yes, but copying should still work.

  1. Can multiple nodes refer to the same random target?

-> Yes, should be preserved.

  1. Time & space constraints?

-> Optimal: O(N) time, O(1) extra space (excluding output) or O(N) with hashmap.

3. Explore examples

Linked List Random Pointers Output
1 → 2 → 3 1 → 3, 2 → 1, 3 → 2 Copy with same structure
1 → 2 1 → None, 2 → 1 Valid copy
[] - []
1 1 → 1 Self pointer preserved

4. Brainstorm 2 - 3 solutions

4.1. Naive Solution - Store a Map by clone to store the address of (next, original) - Time O(N), Space O(N)

  • Loop and clone each node, store {original: clone} in a map.

  • Time: O(N).

  • Space: O(N) extra space for disk.

4.2. Optimal - Clone the next node - Time O(N), Space O(1) no extra space

Store: A → A' → B → B' → C → C'
Original: A → B → C
Copy:     A' → B' → C'

  • Idea: A -> B, so A’ -> B’

  • Time: O(N).

  • Space: O(1), no extra space

5. Implement solutions

5.1. Naive Solution - Time O(N), Space O(N) extra space for dictionary

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        oldToCopy = collections.defaultdict(lambda: Node(0))
        oldToCopy[None] = None

        cur = head
        while cur:
            oldToCopy[cur].val = cur.val
            oldToCopy[cur].next = oldToCopy[cur.next]
            oldToCopy[cur].random = oldToCopy[cur.random]
            cur = cur.next
        return oldToCopy[head]

  • Time: O(N).

  • Space: O(N) extra space for disk.

5.2. Optimal - Clone the next node A -> A’ -> B -> B’ -> C -> C’ - Time O(N), Space O(1) no extra space

# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = x
        self.next = next
        self.random = random

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        cur = head

        # 1️⃣ Insert copied node right after each original node
        while cur:
            copy = Node(cur.val)
            copy.next = cur.next
            cur.next = copy
            cur = copy.next   # move to next original node

        # 2️⃣ Assign random pointers for copy nodes
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next  # move to next original

        # 3️⃣ Separate the two lists
        cur = head
        copy_head = head.next
        copy = copy_head

        while cur:
            cur.next = cur.next.next
            if copy.next:
                copy.next = copy.next.next
            cur = cur.next
            copy = copy.next

        return copy_head

  • Time: O(N).

  • Space: O(1) extra space for disk.

6. Dry run examples

Step List State Notes
Before A → B → C random: A→C, B→A, C→None
Step 1 A → A′ → B → B′ → C → C′ Interleaved
Step 2 Same as above random: A′→C′, B′→A′, C′→None
Step 3 A → B → C and A′ → B′ → C′ Fully separated
November 29, 2025