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.

Practice

1. What is the main challenge when cloning a linked list that has a random pointer in addition to the usual next pointer?

easy

A. Reversing the linked list before cloning

B. Copying the next pointers correctly

C. Ensuring the random pointers in the cloned list point to the correct cloned nodes

D. Sorting the linked list nodes before cloning

Solution

1. Step 1: Understand the structure of the linked list

   The linked list has two pointers: next and random. The next pointer points to the next node in sequence, while the random pointer can point to any node or null.

2. Step 2: Identify the cloning challenge

   When cloning, copying next pointers is straightforward, but random pointers must point to the corresponding cloned nodes, not the original nodes.

3. Final Answer:

   Ensuring the random pointers in the cloned list point to the correct cloned nodes -> Option C

4. Quick Check:

   Random pointer cloning challenge = Ensuring the random pointers in the cloned list point to the correct cloned nodes [OK]

Hint: Focus on mapping original to cloned nodes for random pointers [OK]

Common Mistakes:

• Ignoring random pointers and copying only next pointers
• Setting random pointers to original nodes instead of cloned nodes
• Assuming random pointers are always null or sequential

2. Which of the following Python code snippets correctly creates a new node with the same value as an existing node curr in a linked list with random pointers?

easy

A. new_node = Node(curr)

B. new_node = Node(curr.val)

C. new_node = Node(curr.next)

D. new_node = Node(curr.random)

Solution

1. Step 1: Understand the Node constructor

   The Node constructor takes a value to create a new node. To clone a node, we pass the value of the current node.

2. Step 2: Analyze each option

   new_node = Node(curr.val) passes curr.val, which is the node's value. Options A, C, and D pass node objects or pointers, which is incorrect for creating a new node with the same value.

3. Final Answer:

   new_node = Node(curr.val) -> Option B

4. Quick Check:

   Node creation with value = new_node = Node(curr.val) [OK]

Hint: Use node.val to copy value, not the node itself [OK]

Common Mistakes:

• Passing the node object instead of its value
• Passing next or random pointers instead of value
• Confusing node creation syntax

3. Given the following code snippet to clone a linked list with random pointers, what will be the output of the print statement?

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

def print_list(head):
    curr = head
    result = []
    while curr:
        rand_val = curr.random.val if curr.random else None
        result.append((curr.val, rand_val))
        curr = curr.next
    print(result)

# Original list
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.next = node2
node2.next = node3
node1.random = node3
node2.random = node1
node3.random = node2

# Cloned list (shallow copy for example)
clone1 = Node(1)
clone2 = Node(2)
clone3 = Node(3)
clone1.next = clone2
clone2.next = clone3
clone1.random = node3
clone2.random = node1
clone3.random = node2

print_list(clone1)

medium

A. [(1, 3), (2, 1), (3, 2)]

B. [(1, None), (2, None), (3, None)]

C. [(1, 1), (2, 2), (3, 3)]

D. [(1, 2), (2, 3), (3, 1)]

Solution

1. Step 1: Understand the random pointers in the cloned list

   The cloned nodes' random pointers point to the original nodes (node3, node1, node2), not the cloned nodes.

2. Step 2: Trace the print_list output

   For clone1: val=1, random points to node3 with val=3.
   For clone2: val=2, random points to node1 with val=1.
   For clone3: val=3, random points to node2 with val=2.
   So the printed list is [(1, 3), (2, 1), (3, 2)].

3. Final Answer:

   [(1, 3), (2, 1), (3, 2)] -> Option A

4. Quick Check:

   Random pointers show original node values = [(1, 3), (2, 1), (3, 2)] [OK]

Hint: Check if random points to original or cloned nodes [OK]

Common Mistakes:

• Assuming random points to cloned nodes
• Printing None for random pointers incorrectly
• Mixing up node values in output

4. Consider the following code snippet intended to clone a linked list with random pointers. What is the main bug that will cause incorrect cloning?

def clone_list(head):
    if not head:
        return None
    curr = head
    # Step 1: Create new nodes and insert them after original nodes
    while curr:
        new_node = Node(curr.val)
        new_node.next = curr.next
        curr.next = new_node
        curr = new_node.next
    # Step 2: Assign random pointers for new nodes
    curr = head
    while curr:
        if curr.random:
            curr.next.random = curr.random
        curr = curr.next.next
    # Step 3: Separate the cloned list
    curr = head
    clone_head = head.next
    while curr:
        clone = curr.next
        curr.next = clone.next
        if clone.next:
            clone.next = clone.next.next
        curr = curr.next
    return clone_head

medium

A. Random pointers are assigned incorrectly by missing .next on curr.random

B. Random pointers are assigned to original nodes instead of cloned nodes

C. New nodes are not inserted after original nodes

D. The cloned list is not separated from the original list

Solution

1. Step 1: Analyze random pointer assignment

   In Step 2, the code assigns curr.next.random = curr.random. But curr.random points to an original node, so the cloned node's random pointer points to an original node, not the cloned one.

2. Step 2: Correct assignment

   The correct assignment should be curr.next.random = curr.random.next to point to the cloned node corresponding to curr.random.

3. Final Answer:

   Random pointers are assigned incorrectly by missing .next on curr.random -> Option A

4. Quick Check:

   Random pointer bug = missing .next on curr.random [OK]

Hint: Assign random as curr.next.random = curr.random.next [OK]

Common Mistakes:

• Assigning random pointer directly to original node
• Forgetting to separate cloned list
• Not inserting cloned nodes after originals

5. You want to clone a linked list with random pointers in O(n) time and O(1) extra space. Which approach correctly achieves this? A) Use a hash map to map original nodes to cloned nodes. B) Reverse the original list, clone nodes, then reverse back. C) Create a new list by copying values and random pointers by traversing twice. D) Insert cloned nodes after original nodes, assign random pointers using next pointers, then separate lists.

hard

A. Use a hash map to map original nodes to cloned nodes.

B. Reverse the original list, clone nodes, then reverse back.

C. Create a new list by copying values and random pointers by traversing twice.

D. Insert cloned nodes after original nodes, assign random pointers using next pointers, then separate lists.

Solution

1. Step 1: Understand space and time constraints

   O(n) time means one or two passes over the list. O(1) extra space means no extra data structures like hash maps.

2. Step 2: Analyze each approach

   Use a hash map to map original nodes to cloned nodes. uses extra space (hash map), so not O(1) space.
   Insert cloned nodes after original nodes, assign random pointers using next pointers, then separate lists. inserts cloned nodes between original nodes, uses next pointers to assign random pointers correctly, then separates the lists. This uses no extra space and runs in O(n).
   Create a new list by copying values and random pointers by traversing twice. requires extra space or multiple traversals without the in-place trick.
   Reverse the original list, clone nodes, then reverse back. is unrelated and does not solve the problem efficiently.

3. Final Answer:

   Insert cloned nodes after original nodes, assign random pointers using next pointers, then separate lists. -> Option D

4. Quick Check:

   In-place cloning with next pointers = Insert cloned nodes after original nodes, assign random pointers using next pointers, then separate lists. [OK]

Hint: Insert clones between originals to avoid extra space [OK]

Common Mistakes:

• Using hash maps increases space complexity
• Trying to clone without linking cloned nodes properly
• Ignoring the need to separate cloned list at the end