Skip to main content

Find the balanced node of linked list in c

C program for Find the balanced node of linked list. Here problem description and explanation.

// Include header file
#include <stdio.h>
#include <stdlib.h>
/*
  C program for
  Find the balanced node in a linked list
*/
// Node of LinkedList
typedef struct LinkNode
{
	// Define useful field of LinkNode
	int data;
	struct LinkNode * next;
}LinkNode;

LinkNode * getLinkNode(int data)
{
	// Create dynamic memory of LinkNode
	LinkNode * ref = (LinkNode * ) malloc(sizeof(LinkNode));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	// Set node value
	ref->data = data;
	ref->next = NULL;
	return ref;
}
typedef struct SingleLL
{
	// Define useful field of SingleLL
	struct LinkNode * head;
	struct LinkNode * tail;
}SingleLL;

SingleLL * getSingleLL()
{
	// Create dynamic memory of SingleLL
	SingleLL * ref = (SingleLL * ) malloc(sizeof(SingleLL));
	if (ref == NULL)
	{
		// Failed to create memory 
		return NULL;
	}
	// Set head and tail
	ref->head = NULL;
	ref->tail = NULL;
	return ref;
}
// Insert node at last of linked list
void insert(SingleLL * ref, int value)
{
	// Create a node
	LinkNode * node = getLinkNode(value);
	if (ref->head == NULL)
	{
		// When linked list empty 
		// Add first node
		ref->head = node;
	}
	else
	{
		// Add new node at end of linked list
		ref->tail->next = node;
	}
	ref->tail = node;
}
// Display linked list nodes
void display(SingleLL * ref)
{
	if (ref->head != NULL)
	{
		printf(" Linked List :");
		LinkNode * temp = ref->head;
		while (temp != NULL)
		{
			// Display node data
			printf(" %d ", temp->data);
			// Visit to next node
			temp = temp->next;
		}
	}
	else
	{
		printf("Empty Linked List");
	}
}
void findBalancedNode(SingleLL * ref)
{
	// Define Useful resultant variables
	LinkNode * temp = ref->head;
	LinkNode * result = NULL;
	// Define Useful calculations variables
	int totalSum = 0;
	int currentSum = 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 = ref->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)
	{
		printf("\n Balanced node is : %d\n", result->data);
	}
	else
	{
		printf("\n Balanced node not exist\n");
	}
}
int main()
{
	SingleLL * sll1 = getSingleLL();
	SingleLL * sll2 = getSingleLL();
	SingleLL * sll3 = getSingleLL();
	// Create first linked list
	insert(sll1, 1);
	insert(sll1, 2);
	insert(sll1, 3);
	insert(sll1, 4);
	insert(sll1, 2);
	insert(sll1, 1);
	insert(sll1, 3);
	// Second linked list
	insert(sll2, 1);
	insert(sll2, 3);
	insert(sll2, 6);
	insert(sll2, 1);
	insert(sll2, 1);
	insert(sll2, 1);
	insert(sll2, 1);
	// Third linked list
	insert(sll3, 1);
	insert(sll3, 2);
	insert(sll3, 3);
	// Display node elements
	display(sll1);
	// Find balanced node
	findBalancedNode(sll1);
	// Display node elements
	display(sll2);
	// Find balanced node
	findBalancedNode(sll2);
	// Display node elements
	display(sll3);
	// Find balanced node
	findBalancedNode(sll3);
}

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