Skip to main content

Clone a linked list with random fields in node js

Js program for Clone a linked list with random fields. Here problem description and explanation.

// Node JS Program
// Clone a linked list with next and random field

// Linked List Node
class LinkNode
{
	constructor(data)
	{
		// Set node value
		this.data = data;
		this.next = null;
		this.random = null;
	}
}
class MyLinkedList
{
	constructor()
	{
		this.head = null;
	}
	// Add new node at the end of linked list
	insert(value)
	{
		// Create  node
		var node = new LinkNode(value);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			var temp = this.head;
			// Find last node
			while (temp.next != null)
			{
				// Visit to next node
				temp = temp.next;
			}
			// Add node at last position
			temp.next = 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;
		}
		console.log("-->NULL");
	}
	// Clone the linked list  with next and random field
	cloneList()
	{
		if (this.head == null)
		{
			return null;
		}
		// Define some auxiliary variable
		var temp = null;
		var current = this.head;
		var node = null;
		var front = null;
		// Step 1
		// Create and combine clone node
		while (current != null)
		{
			//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 != null && current.next != null)
		{
			// Clone 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;
		// Step 3
		// 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.cloneList();
	process.stdout.write("\n Actual Linked List");
	list1.display();
	process.stdout.write("\n Clone Linked List");
	list2.display();
}
// Start program execution
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




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