Clone Linked List with Random Pointer in DSA Java - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a new node with the same value as the original node.

DSA Java

Node copy = new Node([1]);

Drag options to blanks, or click blank then click option'

Ahead

Bhead.next

Chead.random

Dhead.val

Attempts:

3 left

💡 Hint

Common Mistakes

Using head.next instead of head.val

Using head.random instead of head.val

Using the whole head node instead of its value

We create a new node with the value of the original node, which is head.val.

2fill in blank

medium

Complete the code to insert the copied node right after the original node.

DSA Java

copy.next = [1].next;
[1].next = copy;

Drag options to blanks, or click blank then click option'

Ahead

Bcopy

Chead.next

Dcopy.next

Attempts:

3 left

💡 Hint

Common Mistakes

Using copy instead of head to access next

Setting pointers in the wrong order

Using head.next.next instead of head.next

We set copy.next to head.next, then set head.next to copy to insert copy after head.

3fill in blank

hard

Fix the error in setting the random pointer of the copied node.

DSA Java

if (head.random != null) {
    head.next.random = head.random[1];
}

Drag options to blanks, or click blank then click option'

A.next

B.random

C.val

D.next.next

Attempts:

3 left

💡 Hint

Common Mistakes

Setting random to head.random instead of head.random.next

Using .random or .val instead of .next

Not checking if head.random is null

The copied node's random pointer should point to the copied version of head.random, which is head.random.next.

4fill in blank

hard

Complete the code to restore the original list and extract the copied list.

DSA Java

Node original = head;
Node copy = head.next;
Node copyHead = copy;

while (original != null) {
    original.next = original.next[1];
    copy.next = copy.next;
    original = original.next;
    copy = copy.next;
}

Drag options to blanks, or click blank then click option'

A.next

B.next.next

D.random

Attempts:

3 left

💡 Hint

Common Mistakes

Setting original.next to original.next instead of original.next.next

Setting copy.next incorrectly causing cycles

Not updating original and copy pointers properly

To restore the original list, set original.next to original.next.next. To link copied nodes, set copy.next to copy.next (empty string means no change if copy.next is null).

5fill in blank

hard

Fill all three blanks to complete the clone function that returns the copied list head.

DSA Java

public Node copyRandomList(Node head) {
    if (head == null) return null;

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

    curr = head;
    while (curr != null) {
        if (curr.random != null) {
            curr.next.random = curr.random[2];
        }
        curr = curr.next.next;
    }

    curr = head;
    Node copyHead = head.next;
    Node copyCurr = copyHead;
    while (curr != null) {
        curr.next = curr.next[3];
        if (copyCurr.next != null) {
            copyCurr.next = copyCurr.next.next;
        }
        curr = curr.next;
        copyCurr = copyCurr.next;
    }

    return copyHead;
}

Drag options to blanks, or click blank then click option'

Acurr.val

B.next

C.next.next

D.random

Attempts:

3 left

💡 Hint

Common Mistakes

Using curr.random instead of curr.random.next

Not restoring original list correctly

Incorrectly linking copied nodes

We create a copy node with curr.val, set random pointer to curr.random.next, and restore original list by setting curr.next to curr.next.next.

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