Clone Linked List with Random Pointer in DSA Python - Execution Trace

Concept Flow - Clone Linked List with Random Pointer

Start with original list

↓

Step 1: Insert cloned nodes after originals

↓

Step 2: Assign random pointers for cloned nodes

↓

Step 3: Separate cloned list from original

↓

Return cloned list head

The process clones nodes by inserting them next to originals, sets random pointers using original's random, then detaches the clone list.

Execution Sample

DSA Python

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

def clone(head):
    # cloning logic here

This code clones a linked list where each node has a next and a random pointer.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Insert cloned nodes after each original node	1->2->3->null	Node1.next = Clone1, Clone1.next = Node2; Node2.next = Clone2, Clone2.next = Node3; Node3.next = Clone3, Clone3.next = null	1->1'->2->2'->3->3'->null
2	Assign random pointers for cloned nodes	1->1'->2->2'->3->3'->null	Clone1.random = Node1.random.next; Clone2.random = Node2.random.next; Clone3.random = Node3.random.next	1(r->3)->1'(r->3')->2(r->1)->2'(r->1')->3(r->2)->3'(r->2')->null
3	Separate cloned list from original	1->2->3->null and 1'->2'->3'->null	Restore original next pointers; set clone next pointers	Original: 1->2->3->null; Clone: 1'->2'->3'->null
4	Return cloned list head	Clone list head at 1'	No pointer changes	Cloned list: 1'->2'->3'->null
5	End	Original and clone separated	No changes	Process complete

💡 All nodes cloned and separated; original list restored; cloned list returned

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	Final
head	1->2->3->null	1->1'->2->2'->3->3'->null	1->1'->2->2'->3->3'->null	1->2->3->null	1->2->3->null
clone_head	null	null	null	1'	1'->2'->3'->null
Node1.next	2	1'	1'	2	2
Clone1.next	null	2	2	2'	2'
Node1.random	3	3	3	3	3
Clone1.random	null	null	3'	3'	3'

Key Moments - 3 Insights

Why do we insert cloned nodes immediately after original nodes instead of creating a separate list first?

Inserting clones next to originals allows easy access to original nodes' random pointers to set clone random pointers correctly, as shown in Step 2 of the execution_table.

How do we assign the random pointer of a cloned node?

We assign clone.random = original.random.next because the clone of any node is right after the original, so original.random.next points to the clone, as shown in Step 2.

Why do we need to separate the cloned list from the original after setting random pointers?

Because after Step 1, original and cloned nodes are interleaved, we restore original next pointers and extract cloned nodes to form a separate list, as shown in Step 3.

Visual Quiz - 3 Questions

Look at the execution_table at Step 1, what is the visual state of the list after inserting cloned nodes?

A 1->2->3->null

B 1->1'->2->2'->3->3'->null

C 1'->2'->3'->null

D 1->2'->3->null

💡 Hint

Check the Visual State column in Step 1 of execution_table

At which step do we assign the random pointers for the cloned nodes?

A Step 2

B Step 1

C Step 3

D Step 4

💡 Hint

Look at the Operation column in execution_table where random pointers are assigned

If we skip Step 3 (separating the cloned list), what would be the state of the list?

A Only cloned nodes remain

B Only original nodes remain

C Original and cloned nodes interleaved

D List is empty

💡 Hint

Refer to the Visual State after Step 1 and Step 2 in execution_table

Concept Snapshot

Clone Linked List with Random Pointer:
1. Insert cloned nodes after originals.
2. Set clone.random = original.random.next.
3. Separate cloned list from original.
4. Return cloned list head.
This preserves original list and clones random pointers correctly.

Full Transcript

To clone a linked list with random pointers, first insert cloned nodes immediately after each original node. This interleaves original and cloned nodes. Next, assign the random pointers of cloned nodes by using the original node's random pointer's next node, which is the clone. Finally, separate the cloned nodes to form the cloned list and restore the original list's next pointers. Return the head of the cloned list. This method ensures the cloned list has correct next and random pointers without extra space for mapping.