Copy List with Random Pointer

Table of Contents +

Copy List with Random Pointer is a favorite because of one twist. Each node points somewhere extra, and that somewhere can be anywhere in the list. So a plain copy will not work. The interviewer wants to see how you keep the old and new nodes matched up while you copy.

🎯 The Problem

You get a linked list with an extra pointer and clone it exactly.

The next pointer goes to the following node, as always.
Each node also has a random pointer. It can point to any node in the list, or to nothing.
Make a deep copy: brand new nodes, not shared ones.
In the copy, the next pointers follow the same path.
The random pointers must point to the matching new nodes, never the old ones.

Input:  list 1 -> 2 -> 3
        1.random -> 3
        2.random -> 1
        3.random -> 2
Output: a brand new list 1 -> 2 -> 3 with the same random links,
        all pointing to the new nodes

Here is the list with its next arrows and one random arrow shown.

🐢 Approach 1: Hash Map Of Old To New (Brute Force)

Map each old node to its new twin, then fix the pointers.

The idea:

A hash map stores a key and a value and looks up the key almost instantly.
Here the key is an old node and the value is its matching new node.
First pass: copy every node and store each pair, old to new.

How it works:

Second pass: for each old node, look up its twin.
Set the twin’s next to the copy of the old next.
Set the twin’s random to the copy of the old random.
The map turns every old pointer into the matching new pointer.

Why it is weak:

The map holds one entry per node, so it needs O(n) extra space.
It is a strong, clear answer, but the map can be skipped entirely.

Here is the old-to-new map code:

def copy_random_list(head):
    old_to_new = {None: None}
    cur = head
    while cur:
        old_to_new[cur] = Node(cur.val)
        cur = cur.next

    cur = head
    while cur:
        old_to_new[cur].next = old_to_new[cur.next]
        old_to_new[cur].random = old_to_new[cur.random]
        cur = cur.next

    return old_to_new[head]

⚡ Approach 2: The Interleaving Trick (Best)

The idea in one line: weave each copy right after its original, so the twin is always the next node.

The idea:

Interleaving means placing each new node directly after its original.
Then you never need a map to find a twin. The twin is the very next node.

How it works:

First pass: for each original, make its copy and slip it in right behind. So 1 -> 2 -> 3 becomes 1 -> 1' -> 2 -> 2' -> 3 -> 3'.
Second pass: set each copy’s random. The copy is original.next. The copy of the random target is original.random.next. So one line does it: copy.random = original.random.next.
Third pass: pull the two lists apart. Restore the original next pointers, and link the copies into their own clean list.

Why it is fast:

No map. Just pointer moves.
The extra space drops to O(1), not counting the copy you must return.

Here is how the list looks after the first interleaving pass.

Steps to Solve

First pass: for each original node, create its copy and insert it right after the original.
Second pass: for each original node, set copy.random = original.random.next, treating a missing random as nothing.
Third pass: separate the woven list into the original list and the copied list, restoring the original next pointers.
Return the head of the copied list.

[data-tabs] [role="tablist"], [data-tabs] [data-scroll] { display: none !important; } [data-tabs] [role="tabpanel"] { display: block !important; } [data-tabs] [role="tabpanel"] + [role="tabpanel"] { margin-top: 1rem; }

This Python version uses a small Node class and the three interleaving passes.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.random = None


def copy_random_list(head):
    if not head:
        return None

    # pass 1: put each copy right after its original
    cur = head
    while cur:
        copy = Node(cur.val)
        copy.next = cur.next
        cur.next = copy
        cur = copy.next

    # pass 2: set the random pointer of each copy
    cur = head
    while cur:
        if cur.random:
            cur.next.random = cur.random.next
        cur = cur.next.next

    # pass 3: split the woven list into two lists
    new_head = head.next
    cur = head
    while cur:
        copy = cur.next
        cur.next = copy.next          # restore original
        if copy.next:
            copy.next = copy.next.next  # link the copies
        cur = cur.next
    return new_head


def print_list(head):
    cur = head
    while cur:
        r = cur.random.val if cur.random else -1
        print("val=" + str(cur.val) + " random=" + str(r))
        cur = cur.next


a = Node(1)
b = Node(2)
c = Node(3)
a.next = b
b.next = c
a.random = c   # 1 -> 3
b.random = a   # 2 -> 1
c.random = b   # 3 -> 2
copied = copy_random_list(a)
print_list(copied)

The output of the above code will be:

val=1 random=3
val=2 random=1
val=3 random=2

Let us walk through the Python version line by line and see why each part is there.

The guard if not head: return None handles the empty list. There is nothing to copy, so we stop.

The first while loop does pass one. For each node we build copy = Node(cur.val). Then copy.next = cur.next makes the copy point where the original pointed. Then cur.next = copy slips the copy right behind the original. The line cur = copy.next jumps over the copy to the next original. So we never copy a copy.

The second while loop does pass two. The key line is cur.next.random = cur.random.next. Read it slowly. cur.next is the copy of the current node. cur.random is the original’s random target. And cur.random.next is the copy of that target, because every copy sits right after its original. So this one line wires the copy’s random to the right new node. We guard it with if cur.random because the random can be nothing.

The third while loop does pass three. We grab copy = cur.next. Then cur.next = copy.next restores the original’s next, so the input list looks untouched. Then if copy.next: copy.next = copy.next.next links each copy to the following copy. The line cur = cur.next moves to the next original. At the end new_head is the first copy, which is the head of our clean new list.

⏱️ Time and Space Complexity

Both ways walk the list a fixed number of times, so both are O(n) time. The hash map way stores one entry per node, so it needs O(n) extra space. The interleaving way stores nothing extra beyond the copy you must return, so its working memory is O(1).

Approach	Time Complexity	Space Complexity
Hash map (old node to new node)	O(n)	O(n)
Interleaving trick	O(n)	O(1)

Tip

The interleaving trick works because a copy always sits right after its original. That single fact replaces the whole hash map. If you can explain that one idea clearly, you have nailed this question.

🧩 Key Takeaways

✅ A deep copy needs brand new nodes, and the random links must point to the new nodes.
✅ The hash map way maps each old node to its new twin, then fixes pointers in a second pass.
✅ The interleaving trick puts each copy right after its original, so the twin is always the next node.
✅ The magic line is copy.random = original.random.next.
✅ Interleaving drops the extra space from O(n) to O(1), since it needs no map.

Check Your Knowledge

4 questions Show quiz Hide quiz

Test what you learned. Pick an answer for each question, then click Check.

🚀 What’s Next?

Find the Duplicate Number
Reorder List

Previous Add Two Numbers Next Find the Duplicate Number

Copy List with Random Pointer

Follow Us

Follow Us