Clone Linked List with Random Pointer in DSA C - 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 randomly to any node in the list or NULL. This structure is used in complex applications like undo operations or social network connections.

🎯 Goal: You will build a program to create a copy (clone) of this linked list with random pointers. The cloned list should be completely separate but have the same values and random connections as the original.

📋 What You'll Learn

Define a Node struct with int val, Node* next, and Node* random.

Create an example linked list with 3 nodes and specific next and random pointers.

Write a function cloneList that clones the list with correct next and random pointers.

Print the original and cloned list showing each node's value and the value of the node pointed by random.

💡 Why This Matters

🌍 Real World

Cloning complex linked data structures is useful in undo-redo systems, copying social network graphs, and replicating game states.

💼 Career

Understanding how to clone linked structures with random pointers is important for software engineers working on advanced data structures, memory management, and system design.

1

Create the linked list nodes with next and random pointers

Define a struct called Node with int val, Node* next, and Node* random. Then create three nodes named node1, node2, and node3 with values 1, 2, and 3 respectively. Set node1.next = &node2, node2.next = &node3, and node3.next = NULL. Set node1.random = &node3, node2.random = &node1, and node3.random = &node2.

DSA C

// Define struct Node and create nodes node1, node2, node3 with next and random pointers
// Your code here

Hint

Start by defining the Node struct with the three fields. Then create three variables of type Node and assign their values and pointers as instructed.

2

Create a helper function to clone the linked list

Write a function called cloneList that takes a pointer to Node called head and returns a pointer to the cloned list's head. For now, just declare the function prototype Node* cloneList(Node* head); above main.

DSA C

#include 
#include 

typedef struct Node {
    int val;
    struct Node* next;
    struct Node* random;
} Node;

// Declare cloneList function
// Your code here

int main() {
    Node node1, node2, node3;

    node1.val = 1;
    node2.val = 2;
    node3.val = 3;

    node1.next = &node2;
    node2.next = &node3;
    node3.next = NULL;

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

    return 0;
}

Hint

Write the function prototype above main so the compiler knows about it before use.

3

Implement the cloneList function to copy nodes with next and random pointers

Implement the cloneList function to clone the linked list with random pointers. Use the following approach:
1. For each node in the original list, create a new node with the same val and insert it right after the original node.
2. Set the random pointer of the new nodes to the new nodes corresponding to the original nodes' random pointers.
3. Separate the new nodes to form the cloned list and restore the original list.
Return the head of the cloned list.

DSA C

#include 
#include 

typedef struct Node {
    int val;
    struct Node* next;
    struct Node* random;
} Node;

Node* cloneList(Node* head) {
    // Your code here
}

int main() {
    Node node1, node2, node3;

    node1.val = 1;
    node2.val = 2;
    node3.val = 3;

    node1.next = &node2;
    node2.next = &node3;
    node3.next = NULL;

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

    return 0;
}

Hint

Follow the three-step approach: insert cloned nodes, assign random pointers, then separate the lists.

4

Print the original and cloned linked lists with random pointers

In main, call cloneList with &node1 and store the result in Node* clonedHead. Then write a function printList that takes Node* head and prints each node's val and the val of the node pointed by random (or NULL if random is NULL). Use printList to print both original and cloned lists.

DSA C

#include 
#include 

typedef struct Node {
    int val;
    struct Node* next;
    struct Node* random;
} Node;

Node* cloneList(Node* head) {
    if (head == NULL) return NULL;

    Node* curr = head;
    while (curr != NULL) {
        Node* newNode = (Node*)malloc(sizeof(Node));
        newNode->val = curr->val;
        newNode->next = curr->next;
        newNode->random = NULL;
        curr->next = newNode;
        curr = newNode->next;
    }

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

    curr = head;
    Node* cloneHead = head->next;
    Node* cloneCurr = cloneHead;

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

    return cloneHead;
}

// Write printList function here
// Your code here

int main() {
    Node node1, node2, node3;

    node1.val = 1;
    node2.val = 2;
    node3.val = 3;

    node1.next = &node2;
    node2.next = &node3;
    node3.next = NULL;

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

    // Call cloneList and print both lists
    // Your code here

    return 0;
}

Hint

Write a printList function that prints each node's value and its random pointer's value or NULL. Then call it for both original and cloned lists.