Clone Linked List with Random Pointer in DSA C

Mental Model

We create a copy of each node and link them so that the new nodes are placed right after the original ones. Then we fix the random pointers of the new nodes by using the original nodes' random pointers.

Analogy: Imagine you have a row of houses (nodes) and each house has a secret friend (random pointer). You build a new house right next to each original house, then you ask each original house to tell its new neighbor who their secret friend is, so the new houses can connect to the right new friends.

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 to fix for clones.

Dry Run Walkthrough

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

Goal: Create a deep copy of the list where each new node has the same value and random pointer as the original, but all nodes are new objects.

Step 1: Insert clone nodes after each original node

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

Why: We place clones next to originals to easily assign random pointers later.

Step 2: Assign random pointers for clone 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: Clone's random pointer is set to original's random's next node (the clone).

Step 3: Separate the combined list into original and cloned lists

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

Why: We restore the 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

#include <stdio.h>
#include <stdlib.h>

// Node structure with value, next and random pointers
typedef struct Node {
    int val;
    struct Node* next;
    struct Node* random;
} Node;

// Create new node
Node* newNode(int val) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->val = val;
    node->next = NULL;
    node->random = NULL;
    return node;
}

// Function to print list with random pointers
void printList(Node* head) {
    Node* curr = head;
    while (curr) {
        printf("%d", curr->val);
        if (curr->random) {
            printf("(rand:%d)", curr->random->val);
        } else {
            printf("(rand:null)");
        }
        if (curr->next) printf(" -> ");
        curr = curr->next;
    }
    printf(" -> null\n");
}

// Clone linked list with random pointer
Node* cloneList(Node* head) {
    if (!head) return NULL;

    Node* curr = head;
    // Step 1: Insert clone nodes after original nodes
    while (curr) {
        Node* copy = newNode(curr->val);
        copy->next = curr->next;
        curr->next = copy;
        curr = copy->next;
    }

    // Step 2: Assign random pointers for clone nodes
    curr = head;
    while (curr) {
        if (curr->random) {
            curr->next->random = curr->random->next;
        }
        curr = curr->next->next;
    }

    // Step 3: Separate original and clone lists
    curr = head;
    Node* cloneHead = head->next;
    Node* cloneCurr = cloneHead;
    while (curr) {
        curr->next = curr->next->next;
        if (cloneCurr->next) {
            cloneCurr->next = cloneCurr->next->next;
        } else {
            cloneCurr->next = NULL;
        }
        curr = curr->next;
        cloneCurr = cloneCurr->next;
    }

    return cloneHead;
}

int main() {
    // Create original list 1->2->3
    Node* n1 = newNode(1);
    Node* n2 = newNode(2);
    Node* n3 = newNode(3);
    n1->next = n2;
    n2->next = n3;

    // Setup random pointers
    n1->random = n3; // 1.random -> 3
    n2->random = n1; // 2.random -> 1
    n3->random = n2; // 3.random -> 2

    printf("Original list:\n");
    printList(n1);

    Node* cloned = cloneList(n1);

    printf("Cloned list:\n");
    printList(cloned);

    return 0;
}

while (curr) { Node* copy = newNode(curr->val); copy->next = curr->next; curr->next = copy; curr = copy->next; }

Insert clone nodes right after each original node to interleave lists

while (curr) { if (curr->random) { curr->next->random = curr->random->next; } curr = curr->next->next; }

Assign clone's random pointer to original's random's clone

while (curr) { curr->next = curr->next->next; if (cloneCurr->next) { cloneCurr->next = cloneCurr->next->next; } else { cloneCurr->next = NULL; } curr = curr->next; cloneCurr = cloneCurr->next; }

Restore original list and extract cloned list by fixing next pointers

Output

Original list:

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

Cloned list:

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

Complexity Analysis

Time: O(n) because we traverse the list a constant number of times proportional to the number of nodes

Space: O(1) extra space because we do not use additional data structures proportional to input size, only pointers manipulation

vs Alternative: Compared to using a hash map to store original-to-clone mapping which uses O(n) extra space, this method is more space efficient

Edge Cases

Empty list (head is NULL)

Function returns NULL immediately without errors

DSA C

if (!head) return NULL;

List with one node whose random pointer is NULL

Cloned list has one node with random pointer NULL

DSA C

if (curr->random) { curr->next->random = curr->random->next; }

Random pointers pointing to self

Cloned node's random pointer points to itself clone

DSA C

curr->next->random = curr->random->next;

When to Use This Pattern

When you see a linked list with an extra random pointer and need to clone it deeply, use the interleaving clone nodes pattern to assign random pointers without extra space.

Common Mistakes

Mistake: Not inserting clone nodes between original nodes, making it hard to assign random pointers correctly
Fix: Interleave clone nodes immediately after original nodes before assigning random pointers

Mistake: Assigning clone random pointers directly from original random pointers without mapping to clones
Fix: Set clone random pointer to original random's next node (the clone)

Mistake: Not restoring the original list after cloning, leaving the list corrupted
Fix: Separate the combined list back into original and cloned lists by fixing next pointers

Summary

Creates a deep copy of a linked list where each node has a random pointer.

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

Interleave cloned nodes with original nodes to assign random pointers without extra space.