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

Concept Flow - Clone Linked List with Random Pointer

Start at head of original list

↓

Create new node for each original node

↓

Insert new node just after original node

↓

Assign random pointers for new nodes

↓

Separate new nodes to form cloned list

↓

Return head of cloned list

We first create new nodes and insert them after original nodes, then assign random pointers for new nodes, and finally separate the cloned list from the original.

Execution Sample

DSA Java

Node cloneList(Node head) {
  // Step 1: Insert cloned nodes
  // Step 2: Set random pointers
  // Step 3: Separate lists
  return clonedHead;
}

This code clones a linked list with random pointers by inserting cloned nodes, setting their random pointers, and separating the cloned list.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Insert cloned nodes after each original node	Original: 1 -> 2 -> 3 -> null	1.next = newNode(1') 1'.next = 2 2.next = newNode(2') 2'.next = 3 3.next = newNode(3') 3'.next = null	1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
2	Assign random pointers for cloned nodes	Original + Clones: 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null	1'.random = 1.random.next (3') 2'.random = 2.random.next (1') 3'.random = 3.random.next (2')	1(r->3) -> 1'(r->3') -> 2(r->1) -> 2'(r->1') -> 3(r->2) -> 3'(r->2')
3	Separate cloned list from original	Combined: 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null	1.next = 2 1'.next = 2' 2.next = 3 2'.next = 3' 3.next = null 3'.next = null	Original: 1 -> 2 -> 3 -> null Clone: 1' -> 2' -> 3' -> null
4	Return cloned list head	Clone head = 1'	No pointer changes	Cloned list head at 1'
5	End	Original and cloned lists separated	No pointer changes	Process complete

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

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	Same	1 -> 2 -> 3 -> null	1 -> 2 -> 3 -> null
clonedHead	null	null	null	1'	1' -> 2' -> 3' -> null
current	1	1	1	1	null
random pointers	1.r->3, 2.r->1, 3.r->2	Same	Cloned nodes assigned random pointers	Same	Same

Key Moments - 3 Insights

Why do we insert cloned nodes immediately after original nodes?

In step 1 (see execution_table row 1), inserting cloned nodes after originals allows easy access to the cloned node from the original node's next pointer, which helps assign random pointers in step 2 without extra space.

How do we assign the random pointer for cloned nodes?

In step 2 (execution_table row 2), the cloned node's random pointer is set to original node's random pointer's next node, which is the cloned version of the original's random target.

How do we separate the cloned list from the combined list?

In step 3 (execution_table row 3), we restore original nodes' next pointers and set cloned nodes' next pointers to form two separate lists, ensuring both lists are correctly linked.

Visual Quiz - 3 Questions

Look at the execution_table at step 2, what is the random pointer of cloned node 2' pointing to?

A Original node 1

B Cloned node 1'

C Original node 3

D Cloned node 3'

💡 Hint

Check execution_table row 2 under Pointer Changes for 2'.random assignment.

At which step do we separate the cloned list from the original list?

A Step 1

B Step 2

C Step 3

D Step 4

💡 Hint

Look at execution_table rows and find where the lists become separate.

If we skip inserting cloned nodes after original nodes, what problem occurs?

A Random pointers cannot be assigned easily

B Original list gets lost

C Cloned list will be empty

D No problem, code works fine

💡 Hint

Refer to key_moments about why insertion after original nodes is important.

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.
This avoids extra space and preserves original list structure.

Full Transcript

To clone a linked list with random pointers, we first create cloned nodes and insert each immediately after its original node. This helps us assign random pointers for cloned nodes by using the original node's random pointer's next node, which is the cloned target. Finally, we separate the combined list into the original and cloned lists by fixing the next pointers. This method clones the list efficiently without extra space for mapping.

Practice

1. What is the main challenge when cloning a linked list with a random pointer?

easy

A. Copying both next and random pointers correctly

B. Only copying the next pointers

C. Ignoring the random pointers

D. Reversing the linked list during cloning

Solution

1. Step 1: Understand linked list structure

   A linked list with random pointers has two references per node: next and random.

2. Step 2: Identify cloning challenge

   Cloning requires copying both next and random pointers so the new list matches the original structure.

3. Final Answer:

   Copying both next and random pointers correctly -> Option A

4. Quick Check:

   Both pointers must be copied = B [OK]

Hint: Remember to copy both next and random pointers [OK]

Common Mistakes:

• Copying only next pointers
• Ignoring random pointers
• Assuming random pointers are null

2. Which Java code snippet correctly declares a node class for a linked list with a random pointer?

easy

A. class Node { int val; Node next; Node random; Node(int val) { val = val; } }

B. class Node { int val; Node next; Node random; Node() { val = 0; } }

C. class Node { int val; Node next; Node random; void Node(int val) { this.val = val; } }

D. class Node { int val; Node next; Node random; Node(int val) { this.val = val; } }

Solution

1. Step 1: Check constructor syntax

   Constructor must have the same name as class and assign value with this.val = val.

2. Step 2: Validate field declarations

   Fields val, next, and random must be declared correctly as int and Node types.

3. Final Answer:

   class Node { int val; Node next; Node random; Node(int val) { this.val = val; } } -> Option D

4. Quick Check:

   Constructor with this.val = val is correct = A [OK]

Hint: Constructor name must match class and use this keyword [OK]

Common Mistakes:

• Using void return type for constructor
• Not using this keyword for assignment
• Incorrect constructor name

3. What will be the output of the following code snippet that clones a linked list with random pointers?

class Node {
  int val;
  Node next, random;
  Node(int val) { this.val = val; }
}

// Original list: 1 -> 2 -> null
// random pointers: 1.random = 2, 2.random = 1

Node head = new Node(1);
head.next = new Node(2);
head.random = head.next;
head.next.random = head;

Node clonedHead = cloneList(head);
System.out.println(clonedHead.val + " -> " + clonedHead.next.val + " -> null");
System.out.println(clonedHead.random.val + " -> " + clonedHead.next.random.val + " -> null");

// Assume cloneList correctly clones the list with random pointers

medium

A. 2 -> 1 -> null
1 -> 2 -> null

B. 1 -> 2 -> null
2 -> 1 -> null

C. 1 -> 2 -> null
1 -> 2 -> null

D. 1 -> 1 -> null
2 -> 2 -> null

Solution

1. Step 1: Understand original list and random pointers

   Original list nodes: 1 -> 2 -> null; random: 1.random = 2, 2.random = 1.

2. Step 2: Cloned list should replicate values and random links

   Cloned list nodes: 1 -> 2 -> null; cloned random pointers: cloned 1.random = cloned 2, cloned 2.random = cloned 1.

3. Final Answer:

   1 -> 2 -> null 2 -> 1 -> null -> Option B

4. Quick Check:

   Random pointers cycle = C [OK]

Hint: Random pointers in clone match original's random targets [OK]

Common Mistakes:

• Printing original random values instead of cloned
• Mixing up random pointer values
• Assuming random pointers are null

4. Identify the bug in this cloning function for a linked list with random pointers:

Node cloneList(Node head) {
  if (head == null) return null;
  Node curr = head;
  while (curr != null) {
    Node copy = new Node(curr.val);
    copy.next = curr.next;
    curr.next = copy;
    curr = curr.next.next;
  }
  // Set random pointers
  curr = head;
  while (curr != null) {
    curr.next.random = curr.random != null ? curr.random.next : null;
    curr = curr.next.next;
  }
  // Separate lists
  curr = head;
  Node copyHead = head.next;
  while (curr != null) {
    Node copy = curr.next;
    curr.next = copy.next;
    copy.next = (copy.next != null) ? copy.next.next : null;
    curr = curr.next;
  }
  return copyHead;
}

medium

A. In the last while loop, copy.next = copy.next.next causes error when copy.next is null

B. In the second while loop, curr.next.random = curr.random.next may cause NullPointerException

C. In the first while loop, curr = curr.next should be curr = curr.next.next

D. The function does not clone the random pointers at all

Solution

1. Step 1: Analyze last while loop for separating lists

   copy.next = copy.next.next assumes copy.next is not null, but at list end copy.next is null causing error.

2. Step 2: Identify fix for null check

   Must check if copy.next is null before accessing copy.next.next to avoid NullPointerException.

3. Final Answer:

   In the last while loop, copy.next = copy.next.next causes error when copy.next is null -> Option A

4. Quick Check:

   Null check needed before copy.next.next = A [OK]

Hint: Check for null before accessing next of next pointers [OK]

Common Mistakes:

• Not checking null before copy.next.next
• Incorrect iteration step in first loop
• Ignoring random pointer cloning

5. Given a linked list with random pointers, how can you clone it in O(n) time and O(1) extra space? Choose the correct approach.

hard

A. Use a hash map to store original to clone node mapping

B. Copy only next pointers and ignore random pointers

C. Interleave cloned nodes with original nodes, set random pointers, then separate lists

D. Create new nodes and assign random pointers by traversing multiple times

Solution

1. Step 1: Understand space constraints

   Using a hash map uses O(n) extra space, so not allowed for O(1) space.

2. Step 2: Use interleaving method

   Interleave cloned nodes between original nodes, assign random pointers using original nodes, then separate lists to get cloned list.

3. Final Answer:

   Interleave cloned nodes with original nodes, set random pointers, then separate lists -> Option C

4. Quick Check:

   Interleaving nodes = O(1) space cloning [OK]

Hint: Interleave clones to avoid extra space for mapping [OK]

Common Mistakes:

• Using hash map increases space complexity
• Multiple traversals without interleaving
• Ignoring random pointers