Clone a Linked List

Linked lists are a foundational data structure, and one common task is cloning a linked list. Cloning involves creating an identical copy of the original linked list, preserving its structure and content. In this article, we will unravel the intricacies of cloning a linked list in C++, exploring its working principles, providing a hands-on implementation, analyzing time and space complexity, and offering a comprehensive understanding of the code.

Working

Cloning a linked list requires more than a simple iteration. We must create a new node for each node in the original list and establish the connections between them to maintain the structure. The challenge arises when dealing with random pointers in a linked list, which may point to arbitrary nodes.

The approach involves three steps:

• Duplicate each node in the original linked list.
• Connect the duplicate nodes in the same order as the original nodes.
• Separate the original and duplicate linked lists.

Complexity

• Time Complexity: O(n), where n is the number of nodes in the linked list. The algorithm iterates through the linked list twice.
• Space Complexity: O(n), where n is the number of nodes in the linked list. Additional space is used to store the duplicate nodes.        

Code

// C++ Code

#include <iostream>
#include <unordered_map>

// Definition for singly-linked list with random pointer
struct Node {
   int data;
   Node* next;
   Node* random;

   Node(int val) : data(val), next(nullptr), random(nullptr) {}
};

// Function to clone a linked list with random pointers
Node* cloneLinkedList(Node* head) {
   if (!head) return nullptr;

   // Step 1: Duplicate each node and insert it after the original node
   Node* current = head;
   while (current) {
       Node* duplicate = new Node(current->data);
       duplicate->next = current->next;
       current->next = duplicate;
       current = duplicate->next;
   }

   // Step 2: Connect random pointers in the duplicate nodes
   current = head;
   while (current) {
       if (current->random) {
           current->next->random = current->random->next;
       }
       current = current->next->next;
   }

   // Step 3: Separate the original and duplicate linked lists
   Node* original = head;
   Node* duplicate = head->next;
   Node* result = head->next;

   while (original) {
       original->next = original->next->next;
       original = original->next;

       if (duplicate->next) {
           duplicate->next = duplicate->next->next;
           duplicate = duplicate->next;
       }
   }

   return result;
}

// Function to print the linked list
void printLinkedList(Node* head) {
   while (head) {
       std::cout << "Data: " << head->data;
       if (head->random) {
           std::cout << " Random Data: " << head->random->data;
       }
       std::cout << std::endl;
       head = head->next;
   }
}

int main() {
   // Create a sample linked list with random pointers
   Node* head = new Node(1);
   head->next = new Node(2);
   head->next->next = new Node(3);
   head->next->next->next = new Node(4);
   head->next->next->next->next = new Node(5);

   // Assign random pointers
   head->random = head->next->next;
   head->next->random = head;
   head->next->next->random = head->next->next->next->next;
   head->next->next->next->random = head->next->next;

   // Clone the linked list
   Node* clonedList = cloneLinkedList(head);

   // Print the original and cloned linked lists
   std::cout << "Original Linked List:" << std::endl;
   printLinkedList(head);

   std::cout << "\nCloned Linked List:" << std::endl;
   printLinkedList(clonedList);

   return 0;
}

Output

Original Linked List:
Data: 1 Random Data: 3
Data: 2 Random Data: 1
Data: 3 Random Data: 5
Data: 4 Random Data: 3
Data: 5

Cloned Linked List:
Data: 1 Random Data: 3
Data: 2 Random Data: 1
Data: 3 Random Data: 5
Data: 4 Random Data: 3
Data: 5

Explanation

• The cloneLinkedList function implements the three-step process described earlier.
• Nodes are duplicated and connected in the original linked list.
• Random pointers in the duplicate nodes are connected.
• The original and duplicate linked lists are separated.
• The printLinkedList function is a utility function to print the linked list.