Clone Linked List with Random Pointer in DSA Java - Build from Scratch

Clone Linked List with Random Pointer

📖 Scenario: Imagine you have a special linked list where each node has two pointers: one points to the next node, and another points to any random node in the list or null. This structure is used in complex applications like undo operations or graph cloning.

🎯 Goal: You will build a program to create a deep copy (clone) of this special linked list. The clone should have new nodes with the same values, next pointers, and random pointers as the original list.

📋 What You'll Learn

Create a Node class with int val, Node next, and Node random fields

Build the original linked list with exact nodes and pointers

Use a helper variable to assist in cloning

Implement the cloning logic to copy nodes and set next and random pointers correctly

Print the cloned list nodes showing val and the val of the random pointer or null

💡 Why This Matters

🌍 Real World

Cloning complex linked data structures is useful in applications like undo-redo systems, graph algorithms, and serialization.

💼 Career

Understanding how to clone linked lists with random pointers is a common interview question and demonstrates mastery of pointers and deep copying.

1

Create the Node class and build the original linked list

Create a Node class with int val, Node next, and Node random fields. Then create three nodes with values 1, 2, and 3. Link them with next pointers: node1 -> node2 -> node3 -> null. Set random pointers as follows: node1.random = node3, node2.random = node1, node3.random = node2.

DSA Java

// Define Node class and create nodes with next and random pointers
// Your code here

Hint

Start by defining the Node class with the required fields and constructor. Then create three nodes and link their next and random pointers exactly as described.

2

Add a helper variable to assist cloning

Inside the main method, create a variable called current and set it to node1. This will help you traverse the original list.

DSA Java

class Node {
    int val;
    Node next;
    Node random;

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

public class Main {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);

        node1.next = node2;
        node2.next = node3;
        node3.next = null;

        node1.random = node3;
        node2.random = node1;
        node3.random = node2;

        // Create a variable called current and set it to node1
        // Your code here
    }
}

Hint

Just create a variable named current and assign it the value node1.

3

Implement the cloning logic for the linked list

Implement the cloning logic inside the main method. First, create new cloned nodes and insert them between original nodes. Then set the random pointers of cloned nodes. Finally, separate the cloned list from the original list. Use variables current, cloneHead, and cloneCurrent as needed.

DSA Java

class Node {
    int val;
    Node next;
    Node random;

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

public class Main {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);

        node1.next = node2;
        node2.next = node3;
        node3.next = null;

        node1.random = node3;
        node2.random = node1;
        node3.random = node2;

        Node current = node1;

        // Insert cloned nodes between original nodes
        // Set random pointers for cloned nodes
        // Separate cloned list from original list
        // Your code here
    }
}

Hint

Follow the three-step approach: insert cloned nodes, assign random pointers, then separate the cloned list. Use current to traverse and create new nodes.

4

Print the cloned linked list with values and random pointers

Add code to print the cloned linked list starting from cloneHead. For each node, print the format: Node val: X, Random points to: Y where X is the node's value and Y is the value of the node pointed by random or null if random is null.

DSA Java

class Node {
    int val;
    Node next;
    Node random;

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

public class Main {
    public static void main(String[] args) {
        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);

        node1.next = node2;
        node2.next = node3;
        node3.next = null;

        node1.random = node3;
        node2.random = node1;
        node3.random = node2;

        Node current = node1;

        // Step 1: Insert cloned nodes between original nodes
        while (current != null) {
            Node cloned = new Node(current.val);
            cloned.next = current.next;
            current.next = cloned;
            current = cloned.next;
        }

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

        // Step 3: Separate cloned list from original list
        current = node1;
        Node cloneHead = node1.next;
        Node cloneCurrent = cloneHead;

        while (cloneCurrent.next != null) {
            current.next = current.next.next;
            cloneCurrent.next = cloneCurrent.next.next;
            current = current.next;
            cloneCurrent = cloneCurrent.next;
        }
        current.next = null; // last original node next to null

        // Print the cloned list nodes with val and random val
        // Your code here
    }
}

Hint

Traverse the cloned list starting from cloneHead. For each node, print its val and the val of its random pointer or null if none.

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