Clone Linked List with Random Pointer in DSA Java - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of cloning a linked list with random pointers

What is the printed output of the cloned linked list's values and their random pointers after running the given Java 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 Solution {
    public Node copyRandomList(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 = copy.next;
        }
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next;
            }
            curr = curr.next.next;
        }
        curr = head;
        Node pseudoHead = new Node(0);
        Node copyCurr = pseudoHead;
        while (curr != null) {
            copyCurr.next = curr.next;
            curr.next = curr.next.next;
            curr = curr.next;
            copyCurr = copyCurr.next;
        }
        return pseudoHead.next;
    }

    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;
        Solution sol = new Solution();
        Node cloned = sol.copyRandomList(n1);
        Node temp = cloned;
        while (temp != null) {
            System.out.print(temp.val + "(" + (temp.random != null ? temp.random.val : "null") + ") -> ");
            temp = temp.next;
        }
        System.out.print("null");
    }
}

A 1(null) -> 2(null) -> 3(null) -> null

B 1(2) -> 2(3) -> 3(1) -> null

C 1(3) -> 2(1) -> 3(2) -> null

D 1(1) -> 2(2) -> 3(3) -> null

💡 Hint

Trace the cloning steps: first interleaving nodes, then assigning random pointers, then separating the lists.

The code first creates a copy node after each original node, then assigns the random pointers of the copied nodes by referencing the original nodes' random pointers' next nodes. Finally, it separates the copied list from the original. The random pointers in the cloned list point to the cloned nodes corresponding to the original random targets.

🧠 Conceptual

intermediate

Understanding the purpose of interleaving nodes in cloning

Why does the cloning algorithm insert copied nodes immediately after their original nodes in the linked list?

A To easily assign the random pointers of copied nodes using original nodes' random pointers.

B To sort the linked list nodes by their values.

C To remove duplicate nodes from the list.

D To reverse the linked list during cloning.

💡 Hint

Think about how the random pointer of a copied node can be set without extra space.

By placing the copied node right after the original, the copied node's random pointer can be set by accessing the original node's random pointer's next node, which is the copied node of the random target. This avoids using extra memory like hash maps.

🔧 Debug

advanced

Identify the error in this cloning code snippet

What error will occur when running this code snippet for cloning a linked list with random pointers?

DSA Java

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

A NullPointerException when accessing curr.next.

B Infinite loop because curr never advances correctly.

C Syntax error due to missing semicolon.

D No error; code runs correctly.

💡 Hint

Check how curr is updated inside the loop.

Inside the loop, curr is updated to curr.next, which is the newly inserted copy node. The next iteration sets copy.next to curr.next again, causing curr to never move past the copy nodes, resulting in an infinite loop.

❓ Predict Output

advanced

Output after cloning and modifying original list

Given the cloning method, what is the output after modifying the original list's random pointer post-cloning?

DSA Java

Node n1 = new Node(1);
Node n2 = new Node(2);
n1.next = n2;
n1.random = n2;
n2.random = n1;
Solution sol = new Solution();
Node cloned = sol.copyRandomList(n1);
n1.random = null;
Node temp = cloned;
while (temp != null) {
    System.out.print(temp.val + "(" + (temp.random != null ? temp.random.val : "null") + ") -> ");
    temp = temp.next;
}
System.out.print("null");

A 1(null) -> 2(null) -> null

B 1(null) -> 2(1) -> null

C 1(1) -> 2(2) -> null

D 1(2) -> 2(1) -> null

💡 Hint

The cloned list is independent of changes to the original list after cloning.

The cloned list's random pointers are set during cloning and do not change when the original list's random pointers are modified later. So the cloned list retains the original random pointer structure.

🚀 Application

expert

How to optimize cloning a linked list with random pointers for space

Which approach uses O(1) extra space to clone a linked list with random pointers?

A Interleave copied nodes with original nodes, assign random pointers, then separate lists.

B Use a hash map to map original nodes to copied nodes and assign pointers.

C Copy nodes and random pointers by deep recursion.

D Create a new list and for each node, search original list for random target.

💡 Hint

Think about how to avoid extra data structures.

Interleaving nodes allows setting random pointers without extra memory. Hash maps use O(n) space. Searching for random targets repeatedly is O(n^2). Recursion can cause stack overflow and does not reduce space complexity.

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