Skip to main content

Find the balanced node of linked list in scala

Scala program for Find the balanced node of linked list. Here problem description and other solutions.

/*
  Scala program for
  Find the balanced node in a linked list
*/
// Node of LinkedList
class LinkNode(var data: Int,
	var next: LinkNode)
{
	def this(data: Int)
	{
		// Set node value
		this(data, null);
	}
}
class SingleLL(var head: LinkNode,
	var tail: LinkNode)
{
	def this()
	{
		this(null, null);
	}
	// Insert node at last of linked list
	def insert(value: Int): Unit = {
		// Create a node
		var node: LinkNode = new LinkNode(value);
		if (this.head == null)
		{
			// When linked list empty 
			// Add first node
			this.head = node;
		}
		else
		{
			// Add new node at end of linked list
			this.tail.next = node;
		}
		this.tail = node;
	}
	// Display linked list nodes
	def display(): Unit = {
		if (this.head != null)
		{
			print(" Linked List :");
			var temp: LinkNode = this.head;
			while (temp != null)
			{
				// Display node data
				print("  " + temp.data);
				// Visit to next node
				temp = temp.next;
			}
		}
		else
		{
			println("Empty Linked List");
		}
	}
	def findBalancedNode(): Unit = {
		// Define Useful resultant variables
		var temp: LinkNode = this.head;
		var result: LinkNode = null;
		// Define Useful calculations variables
		var totalSum: Int = 0;
		var currentSum: Int = 0;
		// Sum of all nodes
		while (temp != null)
		{
			// sum of node value
			totalSum += temp.data;
			// Visit to next node
			temp = temp.next;
		}
		// Get first node of linked list
		temp = this.head;
		while (temp != null && result == null)
		{
			if (totalSum - (currentSum + temp.data) == currentSum)
			{
				// When current node is balanced node
				result = temp;
			}
			// Calculate node sum 
			currentSum += temp.data;
			// Visit to next node
			temp = temp.next;
		}
		if (result != null)
		{
			println("\n Balanced node is : " + result.data);
		}
		else
		{
			println("\n Balanced node not exist");
		}
	}
}
object Main
{
	def main(args: Array[String]): Unit = {
		var sll1: SingleLL = new SingleLL();
		var sll2: SingleLL = new SingleLL();
		var sll3: SingleLL = new SingleLL();
		// Create first linked list
		sll1.insert(1);
		sll1.insert(2);
		sll1.insert(3);
		sll1.insert(4);
		sll1.insert(2);
		sll1.insert(1);
		sll1.insert(3);
		// Second linked list
		sll2.insert(1);
		sll2.insert(3);
		sll2.insert(6);
		sll2.insert(1);
		sll2.insert(1);
		sll2.insert(1);
		sll2.insert(1);
		// Third linked list
		sll3.insert(1);
		sll3.insert(2);
		sll3.insert(3);
		// Display node elements
		sll1.display();
		// Find balanced node
		sll1.findBalancedNode();
		// Display node elements
		sll2.display();
		// Find balanced node
		sll2.findBalancedNode();
		// Display node elements
		sll3.display();
		// Find balanced node
		sll3.findBalancedNode();
	}
}

Output

 Linked List :  1  2  3  4  2  1  3
 Balanced node is : 4
 Linked List :  1  3  6  1  1  1  1
 Balanced node is : 6
 Linked List :  1  2  3
 Balanced node not exist




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