Найдите сбалансированный узел в связанном списке

Опубликовано: 23 Января, 2022

Учитывая связанный список, задача состоит в том, чтобы найти сбалансированный узел в связанном списке. Сбалансированный узел - это узел, в котором сумма всех узлов слева равна сумме всех узлов справа, если такой узел не найден, выведите -1 .

Примеры:

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

Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.

Подход:

Сначала найдите общую сумму значений всех узлов.
Теперь просмотрите связанный список один за другим и во время обхода отслеживайте сумму значений всех предыдущих узлов и найдите сумму оставшегося узла, вычитая текущее значение узла и сумму значений предыдущих узлов из общей суммы.
Сравните обе суммы, если они равны, то текущий узел является требуемым узлом, иначе выведите -1.

Below is the implementation of the above approach:

C++

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
 
// Structure of a node of linked list
class Node {
public:
    int data;
    Node* next;
    Node(int data)
    {
        this->data = data;
        this->next = NULL;
    }
};
  
// Push the new node to front of
// the linked list
Node* push(Node* head, int data)
{
      
    // Return new node as head if
    // head is empty
    if (head == NULL)
    {
        return new Node(data);
    }
    Node* temp = new Node(data);
    temp->next = head;
    head = temp;
    return head;
}
  
// Function to find the balanced node
int findBalancedNode(Node* head)
{
    int tsum = 0;
    Node* curr_node = head;
      
    // Traverse through all node
    // to find the total sum
    while (curr_node != NULL)
    {
        tsum += curr_node->data;
        curr_node = curr_node->next;
    }
  
    // Set current_sum and remaining
    // sum to zero
    int current_sum = 0;
    int remaining_sum = 0;
    curr_node = head;
  
    // Traversing the list to
    // check balanced node
    while (curr_node != NULL)
    {
        remaining_sum = tsum - (current_sum +
                               curr_node->data);
  
        // If sum of the nodes on the left and
        // the current node is equal to the sum
        // of the nodes on the right
        if (current_sum == remaining_sum)
        {
            return curr_node->data;
        }
        current_sum += curr_node->data;
        curr_node = curr_node->next;
    }
    return -1;
}
 
// Driver code
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;
}
 
// This code is contributed by divyehrabadiya07

Java

// Java implementation of the approach
class GFG{
     
// Structure of a node of linked list
static class Node
{
    int data;
    Node next;
     
    Node(int data)
    {
        this.data = data;
        this.next = null;
    }
}
 
// Push the new node to front of
// the linked list
static Node push(Node head, int data)
{
     
    // Return new node as head if
    // head is empty
    if (head == null)
    {
        return new Node(data);
    }
    Node temp = new Node(data);
    temp.next = head;
    head = temp;
    return head;
}
 
// Function to find the balanced node
static int findBalancedNode(Node head)
{
    int tsum = 0;
    Node curr_node = head;
     
    // Traverse through all node
    // to find the total sum
    while (curr_node != null)
    {
        tsum += curr_node.data;
        curr_node = curr_node.next;
    }
 
    // Set current_sum and remaining
    // sum to zero
    int current_sum = 0;
    int remaining_sum = 0;
    curr_node = head;
 
    // Traversing the list to
    // check balanced node
    while (curr_node != null)
    {
        remaining_sum = tsum - (current_sum +
                               curr_node.data);
 
        // If sum of the nodes on the left and
        // the current node is equal to the sum
        // of the nodes on the right
        if (current_sum == remaining_sum)
        {
            return curr_node.data;
        }
        current_sum += curr_node.data;
        curr_node = curr_node.next;
    }
    return -1;
}
 
// Driver code
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));
}
}
 
// This code is contributed by rutvik_56

Python3

# Python3 implementation of the approach
import sys
import math
 
# Structure of a node of linked list
class Node:
    def __init__(self, data):
        self.next = None
        self.data = data
 
# Push the new node to front of the linked list
def push(head, data):
 
    # Return new node as head if head is empty
    if not head:
        return Node(data)
    temp = Node(data)
    temp.next = head
    head = temp
    return head
 
# Function to find the balanced node
def findBalancedNode(head):
    tsum = 0
    curr_node = head
     
    # Traverse through all node
    # to find the total sum
    while curr_node:
        tsum+= curr_node.data
        curr_node = curr_node.next
     
    # Set current_sum and remaining sum to zero
    current_sum, remaining_sum = 0, 0
    curr_node = head
 
    # Traversing the list to check balanced node
    while(curr_node):
        remaining_sum = tsum-(current_sum + curr_node.data)
 
        # If sum of the nodes on the left and the current node
        # is equal to the sum of the nodes on the right
        if current_sum == remaining_sum:
            return curr_node.data
        current_sum+= curr_node.data
        curr_node = curr_node.next
     
    return -1
 
# Driver code
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#

// C# implementation of the approach
using System;
using System.Collections;
using System.Collections.Generic;
class GFG
{
 
  // Structure of a node of linked list
  class Node
  {
    public int data;
    public Node next;
 
    public Node(int data)
    {
      this.data = data;
      this.next = null;
    }
  }
 
  // Push the new node to front of
  // the linked list
  static Node push(Node head, int data)
  {
 
    // Return new node as head if
    // head is empty
    if (head == null)
    {
      return new Node(data);
    }
    Node temp = new Node(data);
    temp.next = head;
    head = temp;
    return head;
  }
 
  // Function to find the balanced node
  static int findBalancedNode(Node head)
  {
    int tsum = 0;
    Node curr_node = head;
 
    // Traverse through all node
    // to find the total sum
    while (curr_node != null)
    {
      tsum += curr_node.data;
      curr_node = curr_node.next;
    }
 
    // Set current_sum and remaining
    // sum to zero
    int current_sum = 0;
    int remaining_sum = 0;
    curr_node = head;
 
    // Traversing the list to
    // check balanced node
    while (curr_node != null)
    {
      remaining_sum = tsum - (current_sum +
                              curr_node.data);
 
      // If sum of the nodes on the left and
      // the current node is equal to the sum
      // of the nodes on the right
      if (current_sum == remaining_sum)
      {
        return curr_node.data;
      }
      current_sum += curr_node.data;
      curr_node = curr_node.next;
    }
    return -1;
  }
 
  // Driver code
  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));
  }
}
 
// This code is contributed by pratham76

Выход:

Сложность времени: O (n)

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

Структуры данных

Найдите сбалансированный узел в связанном списке

C++

Java

Python3

C#

РЕКОМЕНДУЕМЫЕ СТАТЬИ