Skip to main content

Clone a linked list with random fields in swift

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

import Foundation
// Swift 4 Program
// Clone a linked list with next and random field

// Linked List Node
class LinkNode
{
	var data: Int;
	var next: LinkNode? ;
	var random: LinkNode? ;
	init(_ data: Int)
	{
		// Set node value
		self.data = data;
		self.next = nil;
		self.random = nil;
	}
}
class MyLinkedList
{
	var head: LinkNode? ;
	init()
	{
		self.head = nil;
	}
	// Add new node at the end of linked list
	func insert(_ value: Int)
	{
		// Create  node
		let node: LinkNode? = LinkNode(value);
		if (self.head == nil)
		{
			self.head = node;
		}
		else
		{
			var temp: LinkNode? = self.head;
			// Find last node
			while (temp!.next  != nil)
			{
				// Visit to next node
				temp = temp!.next;
			}
			// Add node at last position
			temp!.next = node;
		}
	}
	// Display linked list element
	func display()
	{
		if (self.head == nil)
		{
			print("\nEmpty linked list");
			return;
		}
		var temp: LinkNode? = self.head;
		print(" ");
		while (temp  != nil)
		{
			if ((temp !== self.head))
			{
				print("--->", terminator: "");
			}
			if (temp!.random  != nil)
			{
				print(temp!.data, "("
					,temp!.random!.data ,
                      separator:"", terminator: ")");
			}
			else
			{
				print(temp!.data, terminator: "");
			}
			temp = temp!.next;
		}
		print("-->NULL");
	}
	// Clone the linked list  with next and random field
	func cloneList() -> LinkNode?
	{
		if (self.head == nil)
		{
			return nil;
		}
		// Define some auxiliary variable
		var temp: LinkNode? = nil;
		var current: LinkNode? = self.head;
		var node: LinkNode? = nil;
		var front: LinkNode? = nil;
		// Step 1
		// Create and combine clone node
		while (current  != nil)
		{
			//Get current node of actual linked list
			temp = current;
			// Create clone node
			node = 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 = self.head;
		// Step 2
		// Set actual value of random field in clone linked list
		while (current  != nil && current!.next  != nil)
		{
			// Clone 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;
		// Step 3
		// 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;
	}
	static func main(_ args: [String])
	{
		// 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!.cloneList();
		print("\n Actual Linked List", terminator: "");
		list1!.display();
		print("\n Clone Linked List", terminator: "");
		list2!.display();
	}
}
MyLinkedList.main([String]());

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