Clone Linked List with Random Pointer in DSA Java

Mental Model

We create a new linked list that exactly copies the original list's nodes and their random connections without mixing the two lists.

Analogy: Imagine making a perfect twin of a group of friends standing in a line, where each friend also points randomly to another friend. You first stand each twin right next to their original, then connect their random fingers, and finally separate the twins into their own line.

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

After inserting clones:
1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null
Random pointers not set yet

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

Dry Run Walkthrough

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

Goal: Create a new list that is a deep copy of the original, including random pointers

Step 1: Insert cloned nodes after each original node

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

Why: This helps us link random pointers easily by using the original nodes' next pointers

Step 2: Set random pointers for cloned nodes using original nodes' random pointers

1.random -> 3, 1'.random -> 3'
2.random -> 1, 2'.random -> 1'
3.random -> 2, 3'.random -> 2'

Why: Cloned node's random pointer is the next node of original node's random pointer

Step 3: Separate the cloned list from the original list

Original: 1 -> 2 -> 3 -> null
Cloned: 1' -> 2' -> 3' -> null

Why: We restore the original list and extract the cloned list as a separate copy

Result:

Cloned list: 1' -> 2' -> 3' -> null with random pointers 1'.random=3', 2'.random=1', 3'.random=2'

Annotated Code

DSA Java

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

public class CloneLinkedListWithRandomPointer {
    public static Node cloneList(Node head) {
        if (head == null) return null;

        // Step 1: Insert cloned nodes after original nodes
        Node curr = head;
        while (curr != null) {
            Node clone = new Node(curr.val);
            clone.next = curr.next;
            curr.next = clone;
            curr = clone.next;
        }

        // Step 2: Set random pointers for cloned nodes
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }

        // Step 3: Separate cloned list from original list
        curr = head;
        Node cloneHead = head.next;
        Node cloneCurr = cloneHead;
        while (cloneCurr.next != null) {
            curr.next = curr.next.next;
            cloneCurr.next = cloneCurr.next.next;
            curr = curr.next;
            cloneCurr = cloneCurr.next;
        }
        curr.next = null; // restore last original node

        return cloneHead;
    }

    public static void printList(Node head) {
        Node curr = head;
        while (curr != null) {
            int randomVal = (curr.random != null) ? curr.random.val : -1;
            System.out.print(curr.val + "(random:" + randomVal + ") -> ");
            curr = curr.next;
        }
        System.out.println("null");
    }

    public static void main(String[] args) {
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        n1.next = n2; n2.next = n3;
        n1.random = n3; n2.random = n1; n3.random = n2;

        System.out.println("Original list:");
        printList(n1);

        Node cloned = cloneList(n1);

        System.out.println("Cloned list:");
        printList(cloned);

        System.out.println("Original list after cloning (should be unchanged):");
        printList(n1);
    }
}

while (curr != null) { Node clone = new Node(curr.val); clone.next = curr.next; curr.next = clone; curr = clone.next; }

Insert cloned node immediately after original node to interleave lists

while (curr != null) { if (curr.random != null) { curr.next.random = curr.random.next; } curr = curr.next.next; }

Assign cloned node's random pointer using original node's random pointer's next

while (cloneCurr.next != null) { curr.next = curr.next.next; cloneCurr.next = cloneCurr.next.next; curr = curr.next; cloneCurr = cloneCurr.next; } curr.next = null;

Restore original list and extract cloned list by skipping alternate nodes

Output

Original list:

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

Cloned list:

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

Original list after cloning (should be unchanged):

1(random:3) -> 2(random:1) -> 3(random: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 reuse the original list structure to insert clones without extra data structures

vs Alternative: Naive approach uses a hash map to store original-to-clone mapping with O(n) extra space; this method avoids extra space by interleaving clones

Edge Cases

empty list (head is null)

Returns null immediately without errors

DSA Java

if (head == null) return null;

list with one node and random pointer to itself

Cloned node's random pointer correctly points to itself

DSA Java

if (curr.random != null) { curr.next.random = curr.random.next; }

random pointers are null for all nodes

Cloned nodes' random pointers remain null

DSA Java

if (curr.random != null) { curr.next.random = curr.random.next; }

When to Use This Pattern

When you see a linked list with an extra random pointer and need a deep copy, use the interleaving clone nodes pattern to efficiently copy both next and random pointers.

Common Mistakes

Mistake: Not restoring the original list after cloning, leaving it altered
Fix: Separate the original and cloned lists by skipping alternate nodes to restore original list

Mistake: Setting cloned random pointers incorrectly by not using original node's random's next
Fix: Assign cloned random as curr.next.random = curr.random.next to point to cloned node

Mistake: Not handling null random pointers causing null pointer exceptions
Fix: Check if curr.random is not null before assigning cloned random pointer

Summary

Creates a deep copy of a linked list with next and random pointers by interleaving cloned nodes.

Use when you need to clone complex linked lists with random pointers efficiently without extra space.

The key insight is to insert cloned nodes next to originals to easily assign random pointers and then separate the lists.

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