Clone a linked list with next and random field

Here given code implementation process.

// C Program
// Clone a linked list with next and random field
#include <stdio.h>
 //for malloc function
#include <stdlib.h>

//Linked List Node
struct Node
{
	int data;
	struct Node * next;
	struct Node * random;
};
//Create a node of linked list
struct Node * create_node(int data)
{
	//Create dynamic node
	struct Node * node = (struct Node * ) malloc(sizeof(struct Node));
	if (node == NULL)
	{
		printf("Memory overflow\n");
	}
	else
	{
		//Set initial node value
		node->data = data;
		node->next = NULL;
		node->random = NULL;
	}
	return node;
}
//Add new node at end of linked list 
void insert(struct Node ** head, int data)
{
	struct Node * node = create_node(data);
	if ( * head == NULL)
	{
		* head = node;
	}
	else
	{
		struct Node * temp = * head;
		//Find last node
		while (temp->next != NULL)
		{
			temp = temp->next;
		}
		//Add node at last possition
		temp->next = node;
	}
}
//Display linked list element
void display(struct Node * head)
{
	if (head == NULL)
	{
		printf("\nEmpty linked list\n");
		return;
	}
	struct Node * temp = head;
	printf("\n  ");
	while (temp != NULL)
	{
		if (temp != head)
		{
			printf("--->");
		}
		if (temp->random != NULL)
		{
			printf("%d(%d)", temp->data, temp->random->data);
		}
		else
		{
			printf("%d", temp->data);
		}
		temp = temp->next;
	}
	printf("-->NULL\n");
}
//Clone the linked list  with next and random field
struct Node * clone_list(struct Node * head)
{
	if (head == NULL)
	{
		return NULL;
	}
	// Define some auxiliary variable
	struct Node * temp = NULL;
	struct Node * current = head;
	struct Node * node = NULL;
	struct Node * front = NULL;
	while (current != NULL)
	{
		//Get current node of actual linked list
		temp = current;
		//Create clone node
		node = create_node(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 = head;
	//Set actual value of random field in clone linked list
	while (current != NULL && current->next != NULL)
	{
		//clon list node
		node = current->next;
		if (current->random != NULL)
		{
			//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 = head;
	//Separate actual and clone linked list
	while (current != NULL)
	{
		node = current->next;
		if (front == NULL)
		{
			//Get first node of clone linked list
			front = node;
		}
		current->next = node->next;
		current = current->next;
		if (current != NULL)
		{
			node->next = current->next;
		}
		else
		{
			node->next = NULL;
		}
	}
	return front;
}
int main()
{
	struct Node * list1 = NULL;
	struct Node * list2 = NULL;
	//Create Normal linked list
	insert( & list1, 5);
	insert( & list1, 6);
	insert( & list1, 1);
	insert( & list1, 8);
	insert( & list1, 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->random = list1->next->next->next;
	// 6-->7
	list1->next->random = list1->next->next->next->next;
	// 1 --> 5
	list1->next->next->random = list1;
	// 8 --> 5
	list1->next->next->next->random = list1;
	// 7 --> 6
	list1->next->next->next->next->random = list1->next;
	list2 = clone_list(list1);
	printf("\n  Actual Linked List");
	display(list1);
	printf("\n  Clone Linked List");
	display(list2);
	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
// Java Program
// Clone a linked list with next and random field

//Node of LinkedList
class Node
{
	public int data;
	public Node next;
	public Node random;
	public Node(int data)
	{
		//Set node value
		this.data = data;
		this.next = null;
		this.random = null;
	}
}
class MyLinkedList
{
	public Node head;
	public Node tail;
	//Class constructors
	public MyLinkedList()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	public void insert(int data)
	{
		//Create a node
		Node node = new Node(data);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list element
	public void display()
	{
		if (head == null)
		{
			System.out.print("\nEmpty linked list\n");
			return;
		}
		Node temp = head;
		System.out.print("\n ");
		while (temp != null)
		{
			if (temp != head)
			{
				System.out.print("--->");
			}
			if (temp.random != null)
			{
				System.out.print(temp.data + "(" + temp.random.data + ")");
			}
			else
			{
				System.out.print(temp.data);
			}
			temp = temp.next;
		}
		System.out.print("-->NULL\n");
	}
	//Clone the linked list  with next and random field
	public Node clone_list()
	{
		if (this.head == null)
		{
			return null;
		}
		// Define some auxiliary variable
		Node temp = null;
		Node current = this.head;
		Node node = null;
		Node front = null;
		//create and combine clone node
		while (current != null)
		{
			//Get current node of actual linked list
			temp = current;
			//Create clone node
			node = new Node(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;
		//Set actual value of random field in clone linked list
		while (current != null && current.next != null)
		{
			//clon list node
			node = current.next;
			if (current.random != null)
			{
				//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;
		//Separate actual and clone linked list
		while (current != null)
		{
			node = current.next;
			if (front == null)
			{
				//Get first node of clone linked list
				front = node;
			}
			current.next = node.next;
			current = current.next;
			if (current != null)
			{
				node.next = current.next;
			}
			else
			{
				node.next = null;
			}
		}
		return front;
	}
	public static void main(String[] args)
	{
		//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.clone_list();
		System.out.print("\n Actual Linked List");
		list1.display();
		System.out.print("\n Clone Linked List");
		list2.display();
	}
}

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

//Node of LinkedList
class Node
{
	public: int data;
	Node *next;
	Node *random;
	Node(int data)
	{
		//Set node value
		this->data = data;
		this->next = NULL;
		this->random = NULL;
	}
};
class MyLinkedList
{
	public: Node *head;
	Node *tail;
	//Class constructors
	MyLinkedList()
	{
		this->head = NULL;
		this->tail = NULL;
	}
	//insert node at last of linke list
	void insert(int data)
	{
		//Create a node
		Node *node = new Node(data);
		if (this->head == NULL)
		{
			//When linked list empty add first node
			this->head = node;
			this->tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this->tail->next = node;
			this->tail = node;
		}
	}
	//Display linked list element
	void display()
	{
		if (this->head == NULL)
		{
			cout << "\nEmpty linked list\n";
			return;
		}
		Node *temp = this->head;
		cout << "\n ";
		while (temp != NULL)
		{
			if (temp != this->head)
			{
				cout << "--->";
			}
			if (temp->random != NULL)
			{
				cout << temp->data << "(" << temp->random->data << ")";
			}
			else
			{
				cout << temp->data;
			}
			temp = temp->next;
		}
		cout << "-->NULL\n";
	}
	//Clone the linked list  with next and random field
	Node *clone_list()
	{
		if (this->head == NULL)
		{
			return NULL;
		}
		// Define some auxiliary variable
		Node *temp = NULL;
		Node *current = this->head;
		Node *node = NULL;
		Node *front = NULL;
		//create and combine clone node
		while (current != NULL)
		{
			//Get current node of actual linked list
			temp = current;
			//Create clone node
			node = new Node(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;
		//Set actual value of random field in clone linked list
		while (current != NULL && current->next != NULL)
		{
			//clon list node
			node = current->next;
			if (current->random != NULL)
			{
				//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;
		//Separate actual and clone linked list
		while (current != NULL)
		{
			node = current->next;
			if (front == NULL)
			{
				//Get first node of clone linked list
				front = node;
			}
			current->next = node->next;
			current = current->next;
			if (current != NULL)
			{
				node->next = current->next;
			}
			else
			{
				node->next = NULL;
			}
		}
		return front;
	}
};
int main()
{
	//Test linked list
	MyLinkedList list1 = MyLinkedList();
	MyLinkedList list2 = 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.clone_list();
	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
//Include namespace system
using System;
// C# Program
// Clone a linked list with next and random field

//Node of LinkedList
class Node
{
	public int data;
	public Node next;
	public Node random;
	public Node(int data)
	{
		//Set node value
		this.data = data;
		this.next = null;
		this.random = null;
	}
}
class MyLinkedList
{
	public Node head;
	public Node tail;
	//Class constructors
	public MyLinkedList()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	public void insert(int data)
	{
		//Create a node
		Node node = new Node(data);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list element
	public void display()
	{
		if (head == null)
		{
			Console.Write("\nEmpty linked list\n");
			return;
		}
		Node temp = head;
		Console.Write("\n ");
		while (temp != null)
		{
			if (temp != head)
			{
				Console.Write("--->");
			}
			if (temp.random != null)
			{
				Console.Write(temp.data + "(" + temp.random.data + ")");
			}
			else
			{
				Console.Write(temp.data);
			}
			temp = temp.next;
		}
		Console.Write("-->NULL\n");
	}
	//Clone the linked list  with next and random field
	public Node clone_list()
	{
		if (this.head == null)
		{
			return null;
		}
		// Define some auxiliary variable
		Node temp = null;
		Node current = this.head;
		Node node = null;
		Node front = null;
		//create and combine clone node
		while (current != null)
		{
			//Get current node of actual linked list
			temp = current;
			//Create clone node
			node = new Node(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;
		//Set actual value of random field in clone linked list
		while (current != null && current.next != null)
		{
			//clon list node
			node = current.next;
			if (current.random != null)
			{
				//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;
		//Separate actual and clone linked list
		while (current != null)
		{
			node = current.next;
			if (front == null)
			{
				//Get first node of clone linked list
				front = node;
			}
			current.next = node.next;
			current = current.next;
			if (current != null)
			{
				node.next = current.next;
			}
			else
			{
				node.next = null;
			}
		}
		return front;
	}
	public static void Main(String[] args)
	{
		//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.clone_list();
		Console.Write("\n Actual Linked List");
		list1.display();
		Console.Write("\n Clone Linked List");
		list2.display();
	}
}

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
<?php
// Php Program
// Clone a linked list with next and random field

//Node of LinkedList
class Node
{
	public $data;
	public $next;
	public $random;

	function __construct($data)
	{
		//Set node value
		$this->data = $data;
		$this->next = null;
		$this->random = null;
	}
}
class MyLinkedList
{
	public $head;
	public $tail;
	//Class constructors
	function __construct()
	{
		$this->head = null;
		$this->tail = null;
	}
	//insert node at last of linke list
	public	function insert($data)
	{
		//Create a node
		$node = new Node($data);
		if ($this->head == null)
		{
			//When linked list empty add first node
			$this->head = $node;
			$this->tail = $node;
		}
		else
		{
			//Add new node at end of linked list
			$this->tail->next = $node;
			$this->tail = $node;
		}
	}
	//Display linked list element
	public	function display()
	{
		if ($this->head == null)
		{
			echo "\nEmpty linked list\n";
			return;
		}
		$temp = $this->head;
		echo "\n ";
		while ($temp != null)
		{
			if ($temp != $this->head)
			{
				echo "--->";
			}
			if ($temp->random != null)
			{
				echo $temp->data ."(". $temp->random->data .")";
			}
			else
			{
				echo $temp->data;
			}
			$temp = $temp->next;
		}
		echo "-->NULL\n";
	}
	//Clone the linked list  with next and random field
	public	function clone_list()
	{
		if ($this->head == null)
		{
			return null;
		}
		// Define some auxiliary variable
		$temp = null;
		$current = $this->head;
		$node = null;
		$front = null;
		//create and combine clone node
		while ($current != null)
		{
			//Get current node of actual linked list
			$temp = $current;
			//Create clone node
			$node = new Node($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;
		//Set actual value of random field in clone linked list
		while ($current != null && $current->next != null)
		{
			//clon list node
			$node = $current->next;
			if ($current->random != null)
			{
				//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;
		//Separate actual and clone linked list
		while ($current != null)
		{
			$node = $current->next;
			if ($front == null)
			{
				//Get first node of clone linked list
				$front = $node;
			}
			$current->next = $node->next;
			$current = $current->next;
			if ($current != null)
			{
				$node->next = $current->next;
			}
			else
			{
				$node->next = null;
			}
		}
		return $front;
	}
}

function main()
{
	//Test linked list
	$list1 = new 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->clone_list();
	echo "\n Actual Linked List";
	$list1->display();
	echo "\n Clone Linked List";
	$list2->display();
}
main();

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
// Node Js Program
// Clone a linked list with next and random field

//Node of LinkedList
class Node
{
	constructor(data)
	{
		//Set node value
		this.data = data;
		this.next = null;
		this.random = null;
	}
}
class MyLinkedList
{
	//Class constructors
	constructor()
	{
		this.head = null;
		this.tail = null;
	}
	//insert node at last of linke list
	insert(data)
	{
		//Create a node
		var node = new Node(data);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list element
	display()
	{
		if (this.head == null)
		{
			process.stdout.write("\nEmpty linked list\n");
			return;
		}
		var temp = this.head;
		process.stdout.write("\n ");
		while (temp != null)
		{
			if (temp != this.head)
			{
				process.stdout.write("--->");
			}
			if (temp.random != null)
			{
				process.stdout.write(temp.data + "(" + temp.random.data + ")");
			}
			else
			{
				process.stdout.write(""+temp.data);
			}
			temp = temp.next;
		}
		process.stdout.write("-->NULL\n");
	}
	//Clone the linked list  with next and random field
	clone_list()
	{
		if (this.head == null)
		{
			return null;
		}
		// Define some auxiliary variable
		var temp = null;
		var current = this.head;
		var node = null;
		var front = null;
		//create and combine clone node
		while (current != null)
		{
			//Get current node of actual linked list
			temp = current;
			//Create clone node
			node = new Node(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;
		//Set actual value of random field in clone linked list
		while (current != null && current.next != null)
		{
			//clon list node
			node = current.next;
			if (current.random != null)
			{
				//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;
		//Separate actual and clone linked list
		while (current != null)
		{
			node = current.next;
			if (front == null)
			{
				//Get first node of clone linked list
				front = node;
			}
			current.next = node.next;
			current = current.next;
			if (current != null)
			{
				node.next = current.next;
			}
			else
			{
				node.next = null;
			}
		}
		return front;
	}
}

function main()
{
	//Test linked list
	var list1 = new MyLinkedList();
	var 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.clone_list();
	process.stdout.write("\n Actual Linked List");
	list1.display();
	process.stdout.write("\n Clone Linked List");
	list2.display();
}
main();

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
#  Python 3 Program
#  Clone a linked list with next and random field

# Node of LinkedList
class Node :
	
	def __init__(self, data) :
		# Set node value
		self.data = data
		self.next = None
		self.random = None
	

class MyLinkedList :
	
	# Class constructors
	def __init__(self) :
		self.head = None
		self.tail = None
	
	# insert node at last of linke list
	def insert(self, data) :
		# Create a node
		node = Node(data)
		if (self.head == None) :
			# When linked list empty add first node
			self.head = node
			self.tail = node
		else :
			# Add new node at end of linked list
			self.tail.next = node
			self.tail = node
		
	
	# Display linked list element
	def display(self) :
		if (self.head == None) :
			print("\nEmpty linked list\n", end = "")
			return
		
		temp = self.head
		print("\n ", end = "")
		while (temp != None) :
			if (temp != self.head) :
				print("--->", end = "")
			
			if (temp.random != None) :
				print("{0}(1)".format(temp.data,temp.random.data), end = "")
			else :
				print(temp.data, end = "")
			
			temp = temp.next
		
		print("-->NULL\n", end = "")
	
	# Clone the linked list  with next and random field
	def clone_list(self) :
		if (self.head == None) :
			return None
		
		#  Define some auxiliary variable
		temp = None
		current = self.head
		node = None
		front = None
		# create and combine clone node
		while (current != None) :
			# Get current node of actual linked list
			temp = current
			# Create clone node
			node = Node(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 = self.head
		# Set actual value of random field in clone linked list
		while (current != None and current.next != None) :
			# clon list node
			node = current.next
			if (current.random != None) :
				# 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 = self.head
		# Separate actual and clone linked list
		while (current != None) :
			node = current.next
			if (front == None) :
				# Get first node of clone linked list
				front = node
			
			current.next = node.next
			current = current.next
			if (current != None) :
				node.next = current.next
			else :
				node.next = None
			
		
		return front
	

def main() :
	# Test linked list
	list1 = MyLinkedList()
	list2 = 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.clone_list()
	print("\n Actual Linked List", end = "")
	list1.display()
	print("\n Clone Linked List", end = "")
	list2.display()

if __name__ == "__main__": main()

Output

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

 Clone Linked List
 5(1)--->6(1)--->1(1)--->8(1)--->7(1)-->NULL
#  Ruby Program
#  Clone a linked list with next and random field

# Node of LinkedList
class Node 

	# Define the accessor and reader of class Node  
	attr_reader :data, :next, :random
	attr_accessor :data, :next, :random


	
	def initialize(data)
	
		# Set node value
		self.data = data
		self.next = nil
		self.random = nil
	end
end
class MyLinkedList 

	# Define the accessor and reader of class MyLinkedList  
	attr_reader :head, :tail
	attr_accessor :head, :tail


	
	# Class constructors
	def initialize()
	
		self.head = nil
		self.tail = nil
	end
	# insert node at last of linke list
	def insert(data)
	
		# Create a node
		node = Node.new(data)
		if (self.head == nil)
		
			# When linked list empty add first node
			self.head = node
			self.tail = node
		else
		
			# Add new node at end of linked list
			self.tail.next = node
			self.tail = node
		end
	end
	# Display linked list element
	def display()
	
		if (@head == nil)
		
			print("\nEmpty linked list\n")
			return
		end
		temp = @head
		print("\n ")
		while (temp != nil)
		
			if (temp != @head)
			
				print("--->")
			end
			if (temp.random != nil)
			
				print(temp.data ,"(", temp.random.data ,")")
			else
			
				print(temp.data)
			end
			temp = temp.next
		end
		print("-->NULL\n")
	end
	# Clone the linked list  with next and random field
	def clone_list()
	
		if (self.head == nil)
		
			return nil
		end
		#  Define some auxiliary variable
		temp = nil
		current = self.head
		node = nil
		front = nil
		# create and combine clone node
		while (current != nil)
		
			# Get current node of actual linked list
			temp = current
			# Create clone node
			node = Node.new(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
		end
		# start to actual linked list
		current = self.head
		# Set actual value of random field in clone linked list
		while (current != nil && current.next != nil)
		
			# clon list node
			node = current.next
			if (current.random != nil)
			
				# set random node in clone linked list
				node.random = current.random.next
			end
			# visit to actual linked list next node
			current = node.next
		end
		#  Agian start to actual linked list
		current = self.head
		# Separate actual and clone linked list
		while (current != nil)
		
			node = current.next
			if (front == nil)
			
				# Get first node of clone linked list
				front = node
			end
			current.next = node.next
			current = current.next
			if (current != nil)
			
				node.next = current.next
			else
			
				node.next = nil
			end
		end
		return front
	end
end
def main()

	# Test linked list
	list1 = MyLinkedList.new()
	list2 = MyLinkedList.new()
	# 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.clone_list()
	print("\n Actual Linked List")
	list1.display()
	print("\n Clone Linked List")
	list2.display()
end
main()

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
// Scala Program
// Clone a linked list with next and random field

//Node of LinkedList
class Node(var data: Int,
	var next: Node,
		var random: Node)
{
	def this(data: Int)
	{
		this(data, null, null);
	}
}
class MyLinkedList(var head: Node,
	var tail: Node)
{
	//Class constructors
	def this()
	{
		this(null, null);
	}
	//insert node at last of linke list
	def insert(data: Int): Unit = {
		//Create a node
		var node: Node = new Node(data);
		if (this.head == null)
		{
			//When linked list empty add first node
			this.head = node;
			this.tail = node;
		}
		else
		{
			//Add new node at end of linked list
			this.tail.next = node;
			this.tail = node;
		}
	}
	//Display linked list element
	def display(): Unit = {
		if (head == null)
		{
			print("\nEmpty linked list\n");
			return;
		}
		var temp: Node = head;
		print("\n ");
		while (temp != null)
		{
			if (temp != head)
			{
				print("--->");
			}
			if (temp.random != null)
			{
				print(""+temp.data + "(" + temp.random.data + ")");
			}
			else
			{
				print(temp.data);
			}
			temp = temp.next;
		}
		print("-->NULL\n");
	}
	//Clone the linked list  with next and random field
	def clone_list(): Node = {
		if (this.head == null)
		{
			return null;
		}
		// Define some auxiliary variable
		var temp: Node = null;
		var current: Node = this.head;
		var node: Node = null;
		var front: Node = null;
		//create and combine clone node
		while (current != null)
		{
			//Get current node of actual linked list
			temp = current;
			//Create clone node
			node = new Node(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;
		//Set actual value of random field in clone linked list
		while (current != null && current.next != null)
		{
			//clon list node
			node = current.next;
			if (current.random != null)
			{
				//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;
		//Separate actual and clone linked list
		while (current != null)
		{
			node = current.next;
			if (front == null)
			{
				//Get first node of clone linked list
				front = node;
			}
			current.next = node.next;
			current = current.next;
			if (current != null)
			{
				node.next = current.next;
			}
			else
			{
				node.next = null;
			}
		}
		return front;
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		//Test linked list
		var list1: MyLinkedList = new MyLinkedList();
		var list2: MyLinkedList = 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.clone_list();
		print("\n Actual Linked List");
		list1.display();
		print("\n Clone Linked List");
		list2.display();
	}
}

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
// Swift Program
// Clone a linked list with next and random field

//Node of LinkedList
class Node
{
    var data: Int;
    var next: Node? ;
    var random: Node? ;
    init(_ data: Int)
    {
        //Set node value
        self.data = data;
        self.next = nil;
        self.random = nil;
    }
}
class MyLinkedList
{
    var head: Node? ;
    var tail: Node? ;
    //Class constructors
    init()
    {
        self.head = nil;
        self.tail = nil;
    }
    //insert node at last of linke list
    func insert(_ data: Int)
    {
        //Create a node
        let node: Node? = Node(data);
        if (self.head == nil)
        {
            //When linked list empty add first node
            self.head = node;
            self.tail = node;
        }
        else
        {
            //Add new node at end of linked list
            self.tail!.next = node;
            self.tail = node;
        }
    }
    //Display linked list element
    func display()
    {
        if (self.head == nil)
        {
            print("\nEmpty linked list\n", terminator: "");
            return;
        }
        var temp: Node? = self.head;
        print("\n ", terminator: "");
        while (temp != nil)
        {
            if (!(temp === self.head))
            {
                print("--->", terminator: "");
            }
            if (temp!.random != nil)
            {
                print("\(temp!.data)(\(temp!.random!.data))", terminator: "");
            }
            else
            {
                print(temp!.data, terminator: "");
            }
            temp = temp!.next;
        }
        print("-->NULL\n", terminator: "");
    }
    //Clone the linked list  with next and random field
    func clone_list() -> Node?
    {
        if (self.head == nil)
        {
            return nil;
        }
        // Define some auxiliary variable
        var temp: Node? = nil;
        var current: Node? = self.head;
        var node: Node? = nil;
        var front: Node? = nil;
        //create and combine clone node
        while (current != nil)
        {
            //Get current node of actual linked list
            temp = current;
            //Create clone node
            node = Node(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 = self.head;
        //Set actual value of random field in clone linked list
        while (current != nil && current!.next != nil)
        {
            //clon list node
            node = current!.next;
            if (current!.random != nil)
            {
                //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 = self.head;
        //Separate actual and clone linked list
        while (current != nil)
        {
            node = current!.next;
            if (front == nil)
            {
                //Get first node of clone linked list
                front = node;
            }
            current!.next = node!.next;
            current = current!.next;
            if (current != nil)
            {
                node!.next = current!.next;
            }
            else
            {
                node!.next = nil;
            }
        }
        return front;
    }
}
func main()
{
    //Test linked list
    let list1: MyLinkedList = MyLinkedList();
    let list2: MyLinkedList = 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.clone_list();
    print("\n Actual Linked List", terminator: "");
    list1.display();
    print("\n Clone Linked List", terminator: "");
    list2.display();
}
main();

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

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







© 2021, kalkicode.com, All rights reserved