Skip to main content

Clone a linked list with random fields in java

Java program for Clone a linked list with random fields. Here more information.

// Java Program
// Clone a linked list with next and random field

// Linked List Node
class LinkNode
{
	public int data;
	public LinkNode next;
	public LinkNode random;
	public LinkNode(int data)
	{
		// Set node value
		this.data = data;
		this.next = null;
		this.random = null;
	}
}
class MyLinkedList
{
	public LinkNode head;
	public MyLinkedList()
	{
		this.head = null;
	}
	// Add new node at the end of linked list
	public void insert(int value)
	{
		// Create  node
		LinkNode node = new LinkNode(value);
		if (this.head == null)
		{
			this.head = node;
		}
		else
		{
			LinkNode 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
	public void display()
	{
		if (head == null)
		{
			System.out.print("\nEmpty linked list\n");
			return;
		}
		LinkNode temp = this.head;
		System.out.print("\n ");
		while (temp != null)
		{
			if (temp != this.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.println("-->NULL");
	}
	// Clone the linked list  with next and random field
	public LinkNode cloneList()
	{
		if (this.head == null)
		{
			return null;
		}
		// Define some auxiliary variable
		LinkNode temp = null;
		LinkNode current = this.head;
		LinkNode node = null;
		LinkNode 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;
	}
	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.cloneList();
		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




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