Clone a Linked List with Random Pointers in C

This program demonstrates how to clone a linked list where each node has two pointers: one pointing to the next node in the sequence and another pointing to a random node in the list. This is a typical problem in computer science related to deep copying data structures that contain pointers.

Program Explanation

The program is structured to handle nodes of a linked list, each containing an integer data, a next pointer, and a random pointer. The functions provided include ones to insert new nodes, clone the entire list, and display both the original and cloned lists to verify correctness.

• struct Node: Represents each node in the linked list, containing data, a next pointer, and a random pointer.
• push: Appends a node at the front of the list.
• clone: Clones the linked list with all its next and random pointer configurations.
• printList: Prints out the list to help verify the structure and the random pointers.

Source Code

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

struct Node {
    int data;
    struct Node *next, *random;
};

// Function to create a new Node
struct Node* newNode(int data) {
    struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
    new_node->data = data;
    new_node->next = new_node->random = NULL;
    return new_node;
}

// Function to push a new node to the front of the list
void push(struct Node** head_ref, int data) {
    struct Node* new_node = newNode(data);
    new_node->next = *head_ref;
    *head_ref = new_node;
}

// Function to print the linked list
void printList(struct Node *start) {
    struct Node *ptr = start;
    while (ptr) {
        printf("Data = %d, Random = %d\\n", ptr->data,
            ptr->random ? ptr->random->data : -1);
        ptr = ptr->next;
    }
}

// Actual clone function
struct Node* clone(struct Node *head) {
    struct Node* curr = head, *temp;
    // Insert additional node after every node of original list
    while (curr) {
        temp = curr->next;
        curr->next = newNode(curr->data);
        curr->next->next = temp;
        curr = temp;
    }

    curr = head;
    // Adjust the random pointers of the newly added nodes
    while (curr) {
        if(curr->next)
            curr->next->random = curr->random ? curr->random->next : curr->random;
        curr = curr->next ? curr->next->next : curr->next;
    }

    struct Node* original = head, *copy = head ? head->next : NULL;
    temp = copy;
    // Separate the original list and copied list
    while (original && copy) {
        original->next = original->next ? original->next->next : original->next;
        copy->next = copy->next ? copy->next->next : copy->next;
        original = original->next;
        copy = copy->next;
    }
    return temp;
}

int main() {
    struct Node* start = NULL;
    push(&start, 5);
    push(&start, 4);
    push(&start, 3);
    push(&start, 2);
    push(&start, 1);

    // Setting up random pointers
    start->random = start->next->next;
    start->next->random = start;
    start->next->next->random = start->next->next->next->next;
    start->next->next->next->random = start->next->next;
    start->next->next->next->next->random = start->next;

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

    printf("\\nCloned list:\\n");
    struct Node *cloned_list = clone(start);
    printList(cloned_list);

    return 0;
}
        

Conclusion

The provided C program efficiently clones a linked list with next and random pointers. The method used involves inserting new nodes into the original list, setting up their random pointers using existing links, and then separating the two lists to finalize the clone. This method ensures that all pointers are correctly replicated in the cloned list.