Linked List: Copy a linked list with given next and random pointer

Problem Statement:

You are given a linked list.

Each node will have 2 links, next pointer pointing to the next node and a random pointer, pointing to the random node.

You need to create a copy of LL in O(1) space.

Example:

Solution Explanation:

Solution is very simple.

Create a map of type node.

Then traverse the original array and create new nodes into the map.

Now we have the map that has all the nodes from the original LL.

Next step is to add the links for the next node and the random node.

For that, again traverse the original LL and then update the next pointer and the random pointer to the new node.

Then return the head of the map, we get the result.

Time Complexity: O(2n)
Space Complexity: O(2n)

Code Solution

#include <iostream>
#include <unordered_map>
using namespace std;

//LL node with random and next pointer
class Node 
{
public:

    int data;
    Node* next;
    Node* random;
  
    Node(int x) 
    {
        data = x;
        next = random = NULL;
    }
};

Node* solution(Node* head) 
{
  
    unordered_map<Node*, Node*> mp;
    Node *curr = head;
  
    while (curr != NULL) 
    {
        mp[curr] = new Node(curr->data);
        curr = curr->next;
    }
    
  	curr = head;

    while (curr != NULL) 
    {
      
      	mp[curr]->next = mp[curr->next];
      
      	mp[curr]->random = mp[curr->random];
      
      	curr = curr->next;
    }

    return mp[head];
}

void displayList(Node* head) 
{
    while (head != NULL) 
    {
        cout << head->data << "(";
      	if(head->random)
          	cout << head->random->data << ")";
      	else 
          	cout << "null" << ")";
        
      	if(head->next != NULL)
          	cout << " -> ";
        head = head->next;
    }
    cout << endl;
}

int main() 
{
  
    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);
    head->random = head;
    head->next->random = head->next->next;
    head->next->next->random = head->next;
    head->next->next->next->random = head->next->next;
    head->next->next->next->next->random = head->next;
  
    cout << "Original list:\n";
    displayList(head);
  
    Node* copyList = solution(head);
  
    cout << "Copy list:\n";
    displayList(copyList);
  
    return 0;
}

Output

Original list:
1(1) -> 2(3) -> 3(2) -> 4(3) -> 5(2)
Copy list:
1(1) -> 2(3) -> 3(2) -> 4(3) -> 5(2)