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
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