Clone Linked List with Random Pointer in DSA Python

Mental Model

We want to make a copy of a linked list where each node has two pointers: one to the next node and one to any random node in the list. The challenge is to copy both pointers correctly without mixing original and copied nodes.

Analogy: Imagine you have a chain of people holding hands (next pointer) and each person also points to a random friend in the group (random pointer). Cloning means making a new group with the same hand-holding order and the same random friendships, but with new people.

Original list:
1 -> 2 -> 3 -> null
|    |    |
v    v    v
3    1    2

Each node points to next and random nodes.

Dry Run Walkthrough

Input: list: 1->2->3 with random pointers 1.random->3, 2.random->1, 3.random->2

Goal: Create a new list identical in structure and random links but with new nodes

Step 1: Insert copied node after each original node

1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
Original nodes: 1,2,3
Copied nodes: 1',2',3' inserted right after originals

Why: This helps link copied nodes with their originals for easy random pointer assignment

Step 2: Assign random pointers for copied nodes

1.random->3, so 1'.random->3' (copied 3)
2.random->1, so 2'.random->1'
3.random->2, so 3'.random->2'
List with randoms:
1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
Randoms: 1'.random=3', 2'.random=1', 3'.random=2'

Why: Copied nodes get correct random pointers by using original node's random's next node

Step 3: Separate original and copied nodes to form two lists

Original: 1 -> 2 -> 3 -> null
Copied: 1' -> 2' -> 3' -> null
Both lists have correct next and random pointers

Why: We restore original list and extract the cloned list

Result:

Cloned list:
1' -> 2' -> 3' -> null
Random pointers:
1'.random -> 3'
2'.random -> 1'
3'.random -> 2'

Annotated Code

DSA Python

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

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

    # Step 1: Insert copied nodes after originals
    curr = head
    while curr:
        new_node = Node(curr.val, curr.next)
        curr.next = new_node
        curr = new_node.next

    # Step 2: Assign random pointers for copied nodes
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random.next
        curr = curr.next.next

    # Step 3: Separate original and copied lists
    curr = head
    copy_head = head.next
    copy_curr = copy_head
    while curr:
        curr.next = curr.next.next
        if copy_curr.next:
            copy_curr.next = copy_curr.next.next
        curr = curr.next
        copy_curr = copy_curr.next

    return copy_head

# Driver code to test
# Create nodes
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
# Setup next pointers
node1.next = node2
node2.next = node3
# Setup random pointers
node1.random = node3
node2.random = node1
node3.random = node2

cloned_head = clone_linked_list_with_random(node1)

# Function to print list
# Format: val(random_val) -> ... -> null

def print_list(head):
    curr = head
    res = []
    while curr:
        random_val = curr.random.val if curr.random else 'null'
        res.append(f"{curr.val}({random_val})")
        curr = curr.next
    print(" -> ".join(res) + " -> null")

print_list(cloned_head)

while curr: new_node = Node(curr.val, curr.next) curr.next = new_node curr = new_node.next

Insert copied node after each original node to link originals and copies

while curr: if curr.random: curr.next.random = curr.random.next curr = curr.next.next

Assign random pointer of copied node using original node's random's next

while curr: curr.next = curr.next.next if copy_curr.next: copy_curr.next = copy_curr.next.next curr = curr.next copy_curr = copy_curr.next

Restore original list and extract copied list by skipping alternate nodes

Output

1(3) -> 2(1) -> 3(2) -> null

Complexity Analysis

Time: O(n) because we traverse the list a constant number of times proportional to n nodes

Space: O(1) extra space because we do not use additional data structures, only pointers

vs Alternative: Naive approach uses a hash map to store original-to-copy mapping with O(n) extra space; this method avoids extra space by weaving copied nodes into original list

Edge Cases

Empty list (head is None)

Function returns None immediately without errors

DSA Python

if not head:
        return None

List with one node where random pointer is None

Copied list has one node with random pointer None

DSA Python

if curr.random:
            curr.next.random = curr.random.next

Random pointers pointing to self

Copied nodes' random pointers correctly point to themselves

DSA Python

curr.next.random = curr.random.next

When to Use This Pattern

When you see a linked list with an extra random pointer and need to clone it, use the weaving technique to insert copied nodes between originals to assign random pointers efficiently.

Common Mistakes

Mistake: Not inserting copied nodes between original nodes, causing difficulty in assigning random pointers
Fix: Insert copied nodes immediately after originals to link them for easy random pointer assignment

Mistake: Forgetting to restore the original list after separating the copied list
Fix: Restore original list by skipping copied nodes in the final step

Mistake: Assigning random pointers incorrectly by not using original node's random's next
Fix: Set copied node's random to original node's random's next node

Summary

Clones a linked list with next and random pointers by weaving copied nodes into the original list.

Use when you need a deep copy of a complex linked list with random pointers without extra space.

The key insight is to insert copied nodes right after originals to link random pointers easily.