Clone Linked List with Random Pointer in DSA C#

Mental Model

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

Analogy: Imagine making a perfect twin of a chain of people holding hands, where each person also points randomly to another person in the chain. We want to create a new chain with the same hand-holding and random pointing but separate from the original.

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

Goal: Create a new list:
1' -> 2' -> 3' -> null
with same random links:
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
Random pointers unchanged

Why: This helps link clones with originals to set random pointers easily

Step 2: Assign random pointers for cloned nodes

1.random=3, 1'.random=3'
2.random=1, 2'.random=1'
3.random=2, 3'.random=2'
List: 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> null

Why: Clone's random pointer is original's random's next (the clone)

Step 3: Separate cloned list from original list

Original: 1 -> 2 -> 3 -> null
Clone: 1' -> 2' -> 3' -> null
Random pointers preserved in clone

Why: We restore original list and extract the cloned list

Result:

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

Annotated Code

DSA C#

using System;

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

public class Solution {
    public Node CloneRandomList(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; // advance curr to next original node
        }

        // Step 2: Assign random pointers for cloned nodes
        curr = head;
        while (curr != null) {
            if (curr.random != null) {
                curr.next.random = curr.random.next; // clone.random = original.random.next
            }
            curr = curr.next.next; // move to next original node
        }

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

        return cloneHead;
    }

    public void PrintList(Node head) {
        Node curr = head;
        while (curr != null) {
            string randomVal = curr.random != null ? curr.random.val.ToString() : "null";
            Console.WriteLine($"Node val: {curr.val}, Random val: {randomVal}");
            curr = curr.next;
        }
    }

    public static void Main() {
        // Create original list 1->2->3
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        n1.next = n2;
        n2.next = n3;

        // Setup random pointers
        n1.random = n3;
        n2.random = n1;
        n3.random = n2;

        Solution sol = new Solution();
        Node cloned = sol.CloneRandomList(n1);

        Console.WriteLine("Original list:");
        sol.PrintList(n1);
        Console.WriteLine("Cloned list:");
        sol.PrintList(cloned);
    }
}

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

Insert cloned node after each original node to link clones with originals

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

Assign random pointers for cloned nodes using original nodes' random pointers

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

Separate cloned list from original list restoring original and fixing clone next pointers

Output

Original list:

Node val: 1, Random val: 3

Node val: 2, Random val: 1

Node val: 3, Random val: 2

Cloned list:

Node val: 1, Random val: 3

Node val: 2, Random val: 1

Node val: 3, Random val: 2

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 create cloned nodes in place without extra data structures

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

Edge Cases

Empty list (head is null)

Returns null immediately without processing

DSA C#

if (head == null) return null;

List with one node and random pointer to itself

Cloned list has one node with random pointer to itself

DSA C#

curr.next.random = curr.random.next;

Random pointers are null for all nodes

Cloned nodes have null random pointers as well

DSA C#

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 weaving technique to clone nodes inline for O(1) space cloning.

Common Mistakes

Mistake: Not restoring the original list's next pointers after cloning, leaving the original list broken
Fix: Restore original next pointers in the final step by skipping cloned nodes

Mistake: Assigning random pointers of clones incorrectly by not using original.random.next
Fix: Set clone.random = original.random.next to point to the cloned node

Summary

Creates a deep copy of a linked list with next and random pointers.

Use when you need an exact clone of a complex linked list with random connections.

The key is to weave cloned nodes into the original list to set random pointers without extra space.

Practice

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

easy

A. Reversing the linked list before cloning

B. Sorting the linked list before cloning

C. Copying the next pointers correctly while preserving the random pointers

D. Ignoring the random pointers during cloning

Solution

1. Step 1: Understand the structure of the linked list

   The linked list has two pointers: next and random. The next pointer points to the next node, and the random pointer can point to any node or null.

2. Step 2: Identify the cloning challenge

   While cloning, copying next pointers is straightforward, but random pointers can point anywhere, so they must be copied carefully to preserve the original structure.

3. Final Answer:

   Copying the next pointers correctly while preserving the random pointers -> Option C

4. Quick Check:

   Random pointer preservation = main cloning challenge [OK]

Hint: Remember random pointers can point anywhere, handle them carefully [OK]

Common Mistakes:

• Ignoring random pointers during cloning
• Assuming random pointers follow next pointers
• Trying to sort or reverse the list before cloning

2. Which of the following C# code snippets correctly declares a node class for a linked list with a random pointer?

easy

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

B. public class Node { int val; Node next; Node random; }

C. class Node { public int val; public Node next; }

D. public struct Node { public int val; public Node next; public Node random; }

Solution

1. Step 1: Check for correct access modifiers and constructor

   public class Node { public int val; public Node next; public Node random; public Node(int val) { this.val = val; next = null; random = null; } } declares a public class with public fields and a constructor initializing val, next, and random to null, which is correct.

2. Step 2: Identify issues in other options

   public class Node { int val; Node next; Node random; } lacks access modifiers and constructor. class Node { public int val; public Node next; } misses random pointer. public struct Node { public int val; public Node next; public Node random; } uses struct which is not ideal for linked list nodes.

3. Final Answer:

   Option A code snippet correctly declares the node class -> Option A

4. Quick Check:

   Public class with constructor = correct node declaration [OK]

Hint: Use public class with constructor initializing all pointers [OK]

Common Mistakes:

• Missing public access modifiers
• Not initializing pointers in constructor
• Using struct instead of class for nodes

3. Given the following code snippet for cloning a linked list with random pointers, what will be the output of the cloned list's node values in order?

Node head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(3);
head.random = head.next.next; // 1's random points to 3
head.next.random = head; // 2's random points to 1
head.next.next.random = head.next; // 3's random points to 2

Node clonedHead = CloneLinkedList(head);
Node current = clonedHead;
while (current != null) {
    Console.Write(current.val + " ");
    current = current.next;
}

medium

A. 3 2 1

B. 1 2 3

C. 1 3 2

D. 2 1 3

Solution

1. Step 1: Understand the original list structure

   The original list nodes are 1 -> 2 -> 3 with next pointers in that order. Random pointers do not affect the order of next pointers.

2. Step 2: Cloning preserves next order

   The CloneLinkedList function clones nodes preserving the next pointer order, so the cloned list will have nodes 1 -> 2 -> 3 in sequence.

3. Final Answer:

   1 2 3 -> Option B

4. Quick Check:

   Next pointers order = 1 2 3 [OK]

Hint: Cloning preserves next order; random pointers don't change sequence [OK]

Common Mistakes:

• Confusing random pointer order with next pointer order
• Assuming cloned list reverses nodes
• Printing random pointer values instead of node values

4. Identify the bug in the following CloneLinkedList method that clones a linked list with random pointers:

public Node CloneLinkedList(Node head) {
    if (head == null) return null;
    Node current = head;
    while (current != null) {
        Node copy = new Node(current.val);
        copy.next = current.next;
        current.next = copy;
        current = current.next;
    }
    // Setting random pointers omitted for brevity
    return head.next;
}

medium

A. The method returns the original list head instead of cloned head

B. Random pointers are not set, so cloned list is incomplete

C. The copy node's next pointer is set incorrectly

D. The current pointer update causes an infinite loop

Solution

1. Step 1: Analyze the while loop pointer update

   Inside the loop, current is updated with current = current.next, but after insertion, current.next points to the copy node, so current moves to copy node again, causing an infinite loop.

2. Step 2: Correct pointer update to skip copy node

   To avoid infinite loop, current should be updated to current.next.next to move to the next original node.

3. Final Answer:

   The current pointer update causes an infinite loop -> Option D

4. Quick Check:

   Pointer update must skip copy node to avoid infinite loop [OK]

Hint: Update current to current.next.next after inserting copy [OK]

Common Mistakes:

• Updating current to current.next causes infinite loop
• Forgetting to set random pointers
• Returning original head instead of cloned head

5. You want to clone a linked list with random pointers in O(n) time and O(1) extra space. Which approach correctly achieves this?

hard

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

B. Reverse the original list, clone nodes, then reverse back

C. Create a new list by copying values only, ignoring random pointers

D. Use a hash map to store original to cloned node mappings

Solution

1. Step 1: Understand space and time constraints

   O(n) time and O(1) extra space means no extra data structures like hash maps can be used.

2. Step 2: Use interleaving method

   Interleave cloned nodes between original nodes, set random pointers using original nodes, then separate the two lists. This uses no extra space and runs in linear time.

3. Final Answer:

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

4. Quick Check:

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

Hint: Interleave clones between originals to avoid extra space [OK]

Common Mistakes:

• Using hash map increases space to O(n)
• Ignoring random pointers during cloning
• Reversing list does not help cloning random pointers