Find the balanced node in a Linked List
Last Updated :
17 Aug, 2021
Given a linked list, the task is to find the balanced node in a linked list. A balanced node is a node where the sum of all the nodes on its left is equal to the sum of all the node on its right, if no such node is found then print -1.
Examples:
Input: 1 -> 2 -> 7 -> 10 -> 1 -> 6 -> 3 -> NULL
Output: 10
Sum of nodes on the left of 10 is 1 + 2 + 7 = 10
And, to the right of 10 is 1 + 6 + 3 = 10
Input: 1 -> 5 -> 5 -> 10 -> -3 -> NULL
Output: -1
Approach:
- First, find the total sum of the all node values.
- Now, traverse the linked list one by one and while traversing keep track of all the previous nodes value sum and find the sum of the remaining node by subtracting current node value and the sum of the previous nodes value from the total sum.
- Compare both the sums, if they are equal then current node is the required node else print -1.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
Node(int data)
{
this->data = data;
this->next = NULL;
}
};
Node* push(Node* head, int data)
{
if (head == NULL)
{
return new Node(data);
}
Node* temp = new Node(data);
temp->next = head;
head = temp;
return head;
}
int findBalancedNode(Node* head)
{
int tsum = 0;
Node* curr_node = head;
while (curr_node != NULL)
{
tsum += curr_node->data;
curr_node = curr_node->next;
}
int current_sum = 0;
int remaining_sum = 0;
curr_node = head;
while (curr_node != NULL)
{
remaining_sum = tsum - (current_sum +
curr_node->data);
if (current_sum == remaining_sum)
{
return curr_node->data;
}
current_sum += curr_node->data;
curr_node = curr_node->next;
}
return -1;
}
int main()
{
Node* head = NULL;
head = push(head, 3);
head = push(head, 6);
head = push(head, 1);
head = push(head, 10);
head = push(head, 7);
head = push(head, 2);
head = push(head, 1);
cout << findBalancedNode(head);
return 0;
}
|
Java
class GFG{
static class Node
{
int data;
Node next;
Node(int data)
{
this.data = data;
this.next = null;
}
}
static Node push(Node head, int data)
{
if (head == null)
{
return new Node(data);
}
Node temp = new Node(data);
temp.next = head;
head = temp;
return head;
}
static int findBalancedNode(Node head)
{
int tsum = 0;
Node curr_node = head;
while (curr_node != null)
{
tsum += curr_node.data;
curr_node = curr_node.next;
}
int current_sum = 0;
int remaining_sum = 0;
curr_node = head;
while (curr_node != null)
{
remaining_sum = tsum - (current_sum +
curr_node.data);
if (current_sum == remaining_sum)
{
return curr_node.data;
}
current_sum += curr_node.data;
curr_node = curr_node.next;
}
return -1;
}
public static void main(String []args)
{
Node head = null;
head = push(head, 3);
head = push(head, 6);
head = push(head, 1);
head = push(head, 10);
head = push(head, 7);
head = push(head, 2);
head = push(head, 1);
System.out.println(findBalancedNode(head));
}
}
|
Python3
import sys
import math
class Node:
def __init__(self, data):
self.next = None
self.data = data
def push(head, data):
if not head:
return Node(data)
temp = Node(data)
temp.next = head
head = temp
return head
def findBalancedNode(head):
tsum = 0
curr_node = head
while curr_node:
tsum+= curr_node.data
curr_node = curr_node.next
current_sum, remaining_sum = 0, 0
curr_node = head
while(curr_node):
remaining_sum = tsum-(current_sum + curr_node.data)
if current_sum == remaining_sum:
return curr_node.data
current_sum+= curr_node.data
curr_node = curr_node.next
return -1
if __name__=='__main__':
head = None
head = push(head, 3)
head = push(head, 6)
head = push(head, 1)
head = push(head, 10)
head = push(head, 7)
head = push(head, 2)
head = push(head, 1)
print(findBalancedNode(head))
|
C#
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
class Node
{
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
static Node push(Node head, int data)
{
if (head == null)
{
return new Node(data);
}
Node temp = new Node(data);
temp.next = head;
head = temp;
return head;
}
static int findBalancedNode(Node head)
{
int tsum = 0;
Node curr_node = head;
while (curr_node != null)
{
tsum += curr_node.data;
curr_node = curr_node.next;
}
int current_sum = 0;
int remaining_sum = 0;
curr_node = head;
while (curr_node != null)
{
remaining_sum = tsum - (current_sum +
curr_node.data);
if (current_sum == remaining_sum)
{
return curr_node.data;
}
current_sum += curr_node.data;
curr_node = curr_node.next;
}
return -1;
}
public static void Main(string []args)
{
Node head = null;
head = push(head, 3);
head = push(head, 6);
head = push(head, 1);
head = push(head, 10);
head = push(head, 7);
head = push(head, 2);
head = push(head, 1);
Console.Write(findBalancedNode(head));
}
}
|
Javascript
<script>
class Node {
constructor(data) {
this.data = data;
this.next = null;
}
}
function push( head, data)
{
if (head == null)
{
return new Node(data);
}
var temp = new Node(data);
temp.next = head;
head = temp;
return head;
}
function findBalancedNode( head)
{
let tsum = 0;
let curr_node = head;
while (curr_node != null)
{
tsum += curr_node.data;
curr_node = curr_node.next;
}
let current_sum = 0;
let remaining_sum = 0;
curr_node = head;
while (curr_node != null)
{
remaining_sum = tsum - (current_sum +
curr_node.data);
if (current_sum == remaining_sum)
{
return curr_node.data;
}
current_sum += curr_node.data;
curr_node = curr_node.next;
}
return -1;
}
var head = null;
head = push(head, 3);
head = push(head, 6);
head = push(head, 1);
head = push(head, 10);
head = push(head, 7);
head = push(head, 2);
head = push(head, 1);
document.write(findBalancedNode(head));
</script>
|
Time Complexity: O(n)
Auxiliary Space: O(1)