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

Concept Flow - Clone Linked List with Random Pointer

Create new nodes interleaved with original nodes

↓

Assign random pointers for new nodes using original nodes

↓

Separate the new nodes to form the cloned list

↓

Return head of cloned list

The cloning process first creates new nodes inserted between original nodes, then sets random pointers for these new nodes, and finally separates the new nodes to form the cloned list.

Execution Sample

DSA C

Node* cloneList(Node* head) {
  Node* curr = head;
  while (curr) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->val = curr->val;
    newNode->next = curr->next;
    curr->next = newNode;
    curr = newNode->next;
  }
  // Set random pointers and separate lists
}

This code snippet clones nodes by inserting new nodes after each original node.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Start with original list	1->2->3->null	head points to 1	1(val, random) -> 2(val, random) -> 3(val, random) -> null
2	Insert new node after 1	1->1'->2->3->null	1.next = 1', 1'.next = 2	1 -> 1' -> 2 -> 3 -> null
3	Insert new node after 2	1->1'->2->2'->3->null	2.next = 2', 2'.next = 3	1 -> 1' -> 2 -> 2' -> 3 -> null
4	Insert new node after 3	1->1'->2->2'->3->3'->null	3.next = 3', 3'.next = null	1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
5	Assign random for 1'	Same nodes	1'.random = 1.random ? 1.random.next : NULL	1'.random points to clone of 1.random
6	Assign random for 2'	Same nodes	2'.random = 2.random ? 2.random.next : NULL	2'.random points to clone of 2.random
7	Assign random for 3'	Same nodes	3'.random = 3.random ? 3.random.next : NULL	3'.random points to clone of 3.random
8	Separate cloned list from original	Original: 1->2->3->null Clone: 1'->2'->3'->null	Restore original next pointers, set clone next pointers	Two separate lists: original and cloned
9	Return cloned list head	Clone list head is 1'	Return pointer to 1'	Cloned list ready
10	End	Process complete	No pointer changes	Original and cloned lists separated

💡 All nodes cloned, random pointers assigned, and lists separated

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 8	Final
curr	points to 1	points to 2	points to 3	null	null	null
head	points to 1	points to 1	points to 1	points to 1	points to 1	points to 1
newNode	null	points to 1'	points to 2'	points to 3'	null	null
cloneHead	null	null	null	null	points to 1'	points to 1'

Key Moments - 3 Insights

Why do we insert new nodes between original nodes instead of creating a separate list immediately?

Inserting new nodes between original nodes allows easy access to the corresponding cloned node when assigning random pointers, as shown in steps 2-4 and 5-7 in the execution_table.

How do we assign the random pointer for the cloned nodes?

We assign the cloned node's random pointer by using the original node's random pointer's next node, which is the cloned node, as shown in steps 5-7.

How do we separate the cloned list from the original list without losing connections?

We restore the original nodes' next pointers and set the cloned nodes' next pointers to form a separate list, as done in step 8.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the visual state of the list?

A 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null

B 1 -> 2 -> 3 -> null

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

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

💡 Hint

Refer to the Visual State column at step 4 in the execution_table.

At which step do we assign the random pointer for the cloned node of 2?

A Step 2

B Step 6

C Step 5

D Step 8

💡 Hint

Check the Operation column for assigning random pointers in the execution_table.

If we skip step 8 (separating the lists), 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 Lists are already separated

💡 Hint

Look at the Pointer Changes and Visual State columns before step 8.

Concept Snapshot

Clone Linked List with Random Pointer:
1. Insert cloned nodes after each original node.
2. Assign cloned nodes' random pointers using original nodes' random.next.
3. Separate cloned nodes to form the cloned list.
4. Return cloned list head.
This method avoids extra space by interleaving nodes.

Full Transcript

To clone a linked list with random pointers, first insert new cloned nodes between original nodes. Then assign the random pointers of cloned nodes by referencing the original nodes' random pointers' next nodes. Finally, separate the cloned nodes from the original list to form a new cloned list. This process is efficient and uses no extra space for mapping. The execution table shows each step with the list's visual state and pointer changes, helping understand how the list transforms during cloning.