Skip to main content

Fold linked list in kotlin

Kotlin program for Fold linked list. Here problem description and explanation.

/*
  Kotlin program for
  Fold linked list
*/
// Linked list node
class LinkNode
{
	var data: Int;
	var next: LinkNode ? ;
	constructor(data: Int)
	{
		this.data = data;
		this.next = null;
	}
}
class SingleLL
{
	var head: LinkNode ? ;
	constructor()
	{
		this.head = null;
	}
	// Add node at the beginning
	fun addNode(data: Int): Unit
	{
		// Create new node
		val node: LinkNode = LinkNode(data);
		node.next = this.head;
		// Set new head
		this.head = node;
	}
	// Display linked list element
	fun display(): Unit
	{
		if (this.head == null)
		{
			return;
		}
		var temp: LinkNode ? = this.head;
		// iterating linked list elements
		while (temp != null)
		{
			print(" " + temp.data + " →");
			// Visit to next node
			temp = temp.next;
		}
		println(" NULL");
	}
	// This is handle the request of 
	// folding given linked list nodes
	fun foldList(): Unit
	{
		if (this.head == null)
		{
			print("\n Empty linked list");
			return;
		}
		// Some auxiliary variables
		var temp: LinkNode ? = this.head;
		var auxiliary: LinkNode ? = this.head;
		var hold: LinkNode ? ;
		// Loops used to find the middle node
		while (temp != null && temp.next != null && 
          temp.next?.next != null)
		{
			// Visit to next node
			auxiliary = auxiliary?.next;
			// Visit to second next node
			temp = temp.next?.next;
		}
		if (auxiliary != null)
		{
			hold = auxiliary;
			auxiliary = auxiliary.next;
			// Separating half nodes
			hold.next = null;
			// Start with first node of next half section
			temp = auxiliary;
			auxiliary = null;
			// Reverse second half nodes 
			while (temp != null)
			{
				hold = temp;
				temp = temp.next;
				hold.next = auxiliary;
				auxiliary = hold;
			}
			// Start with first node of linked list
			temp = this.head;
			// Combine first and second half nodes 
			// in alternate manner
			while (temp != null)
			{
				hold = temp;
				temp = temp.next;
				hold.next = auxiliary;
				if (auxiliary != null)
				{
					hold = auxiliary;
					auxiliary = auxiliary.next;
					hold.next = temp;
				}
			}
		}
	}
}
fun main(args: Array < String > ): Unit
{
	// Create a empty linked lists
	val sll1: SingleLL = SingleLL();
	val sll2: SingleLL = SingleLL();
	//  Constructed first linked list
	//  1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
	sll1.addNode(8);
	sll1.addNode(7);
	sll1.addNode(6);
	sll1.addNode(5);
	sll1.addNode(4);
	sll1.addNode(3);
	sll1.addNode(2);
	sll1.addNode(1);
	// Constructed second linked list
	//  1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
	sll2.addNode(7);
	sll2.addNode(6);
	sll2.addNode(5);
	sll2.addNode(4);
	sll2.addNode(3);
	sll2.addNode(2);
	sll2.addNode(1);
	// Test A
	println(" Before folding");
	sll1.display();
	// Form of folding
	//      1 → 2 → 3 → 4 ──┐
	// NULL ← 8 ← 7 ← 6 ← 5⤶
	sll1.foldList();
	// After merging
	// 1 → 8 → 2 → 7 → 3 → 6 → 4 → 5 → NULL
	println(" After folding");
	sll1.display();
	// Test B
	println(" Before folding");
	sll2.display();
	// Form of folding
	//      1 → 2 → 3 → 4 
	// NULL ← 7 ← 6 ← 5⤶
	sll2.foldList();
	// After merging
	// 1 → 7 → 2 → 6 → 3 → 5 → 4 → NULL
	println(" After folding");
	sll2.display();
}

Output

 Before folding
 1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → NULL
 After folding
 1 → 8 → 2 → 7 → 3 → 6 → 4 → 5 → NULL
 Before folding
 1 → 2 → 3 → 4 → 5 → 6 → 7 → NULL
 After folding
 1 → 7 → 2 → 6 → 3 → 5 → 4 → 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