Skip to main content

Clone a linked list with next and random pointer in c++

C++ program for Clone a linked list with next and random pointer. Here problem description and explanation.

// Include header file
#include <iostream>
using namespace std;
// C++ Program
// Clone a linked list with next and random field

// Linked List Node
class LinkNode
{
	public: int data;
	LinkNode *next;
	LinkNode *random;
	LinkNode(int data)
	{
		// Set node value
		this->data = data;
		this->next = nullptr;
		this->random = nullptr;
	}
};
class MyLinkedList
{
	public: LinkNode *head;
	MyLinkedList()
	{
		this->head = nullptr;
	}
	// Add new node at the end of linked list
	void insert(int value)
	{
		// Create  node
		LinkNode *node = new LinkNode(value);
		if (this->head == nullptr)
		{
			this->head = node;
		}
		else
		{
			LinkNode *temp = this->head;
			// Find last node
			while (temp->next != nullptr)
			{
				// Visit to next node
				temp = temp->next;
			}
			// Add node at last position
			temp->next = node;
		}
	}
	// Display linked list element
	void display()
	{
		if (this->head == nullptr)
		{
			cout << "\nEmpty linked list\n";
			return;
		}
		LinkNode *temp = this->head;
		cout << "\n ";
		while (temp != nullptr)
		{
			if (temp != this->head)
			{
				cout << "--->";
			}
			if (temp->random != nullptr)
			{
				cout << temp->data 
                     << "(" << temp->random->data << ")";
			}
			else
			{
				cout << temp->data;
			}
			temp = temp->next;
		}
		cout << "-->NULL" << endl;
	}
	// Clone the linked list  with next and random field
	LinkNode *cloneList()
	{
		if (this->head == nullptr)
		{
			return nullptr;
		}
		// Define some auxiliary variable
		LinkNode *temp = nullptr;
		LinkNode *current = this->head;
		LinkNode *node = nullptr;
		LinkNode *front = nullptr;
		// Step 1
		// Create and combine clone node
		while (current != nullptr)
		{
			//Get current node of actual linked list
			temp = current;
			// Create clone node
			node = new LinkNode(current->data);
			// Visit to next node
			current = current->next;
			// Connect clone node after actual node
			temp->next = node;
			// Binding this clone to next upcoming
			// nodes in actual linked list
			node->next = current;
		}
		// Start to actual linked list
		current = this->head;
		// Step 2
		// Set actual value of random field in clone linked list
		while (current != nullptr && current->next != nullptr)
		{
			// Clone list node
			node = current->next;
			if (current->random != nullptr)
			{
				// Set random node in clone linked list
				node->random = current->random->next;
			}
			// Visit to actual linked list next node
			current = node->next;
		}
		// Agian start to actual linked list
		current = this->head;
		// Step 3
		// Separate actual and clone linked list
		while (current != nullptr)
		{
			node = current->next;
			if (front == nullptr)
			{
				// Get first node of clone linked list
				front = node;
			}
			current->next = node->next;
			current = current->next;
			if (current != nullptr)
			{
				node->next = current->next;
			}
			else
			{
				node->next = nullptr;
			}
		}
		return front;
	}
};
int main()
{
	// Test linked list
	MyLinkedList *list1 = new MyLinkedList();
	MyLinkedList *list2 = new MyLinkedList();
	// Create Normal linked list
	list1->insert(5);
	list1->insert(6);
	list1->insert(1);
	list1->insert(8);
	list1->insert(7);
	/*
	   Simple linked list
	   5 → 6 → 1 → 8 → 7 → NULL
	   Set random node value
	   ╷───────────┐
	   │           │
	   │   ╷───────│───┐
	   ↓───│───╷   │   │
	   ↓   ↓   ↑   │   │
	   5 → 6 → 1 → 8 → 7 → NULL
	   │   │       ↑   │
	   └───│───────┘   │    
	       │           │
	       └───────────┘ 
	    5(8)-->6(7)-->1(5)-->8(5)-->7(6)-->NULL
	    Linked list with random field
	*/
	// 5-->8
	list1->head->random = list1->head->next->next->next;
	// 6-->7
	list1->head->next->random = list1->head->next->next->next->next;
	// 1 --> 5
	list1->head->next->next->random = list1->head;
	// 8 --> 5
	list1->head->next->next->next->random = list1->head;
	// 7 --> 6
	list1->head->next->next->next->next->random = list1->head->next;
	list2->head = list1->cloneList();
	cout << "\n Actual Linked List";
	list1->display();
	cout << "\n Clone Linked List";
	list2->display();
	return 0;
}

Output

 Actual Linked List
 5(8)--->6(7)--->1(5)--->8(5)--->7(6)-->NULL

 Clone Linked List
 5(8)--->6(7)--->1(5)--->8(5)--->7(6)-->NULL




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment