Absolute difference between sum of alternate node of Linked List
Given a singly linked list containing N nodes, the task is to find the absolute difference between the sum of an alternate node of the linked list.
Examples:
Input: List = 15 -> 16 -> 6 -> 7 -> 17
Output: 15
Explanation: sum1 = 15 + 6 + 17 = 38, sum2 = 16 + 7 = 23, absolute diff = abs(38-23) = 15Input: List = 3 -> 4 -> 2 -> 9
Output: 8
Explanation: sum1 = 3 + 2 = 5, sum2 = 4 + 9 = 13 absolute diff = abs(5-13) = 8
Approach: To solve the problem follow the below idea:
The idea is to traverse the nodes of the singly linked list one by one and check if the current node is contributing to sum1(odd position) or sum2(even position). then return the absolute difference between them.
Below is the implementation of the above idea:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Linked List Node struct Node { int data; Node* next; Node( int val) : data(val) , next(nullptr) { } }; // Function to calculate absolute // difference between sum of alternate nodes int getAbsoluteDiff(Node* head) { int sum1 = 0, sum2 = 0; bool flag = true ; while (head != nullptr) { // Based on flag decision made if (flag) { sum1 += head->data; } else { sum2 += head->data; } flag = !flag; head = head->next; } return abs (sum1 - sum2); } // Driver code int main() { // Create a sample linked list: // 15 -> 16 -> 6 -> 7 -> 17 Node* head = new Node(15); head->next = new Node(16); head->next->next = new Node(6); head->next->next->next = new Node(7); head->next->next->next->next = new Node(17); // Function Call cout << "Absolute Difference between sum of alternate " "nodes: " << getAbsoluteDiff(head) << endl; return 0; } |
Java
// Linked List Node class Node { int data; Node next; Node( int val) { data = val; next = null ; } } public class AlternateNodeSumDifference { // Function to calculate absolute // difference between sum of alternate nodes static int getAbsoluteDiff(Node head) { int sum1 = 0 , sum2 = 0 ; boolean flag = true ; while (head != null ) { // Based on flag decision made if (flag) { sum1 += head.data; } else { sum2 += head.data; } flag = !flag; head = head.next; } return Math.abs(sum1 - sum2); } // Driver code public static void main(String[] args) { // Create a sample linked list: // 15 -> 16 -> 6 -> 7 -> 17 Node head = new Node( 15 ); head.next = new Node( 16 ); head.next.next = new Node( 6 ); head.next.next.next = new Node( 7 ); head.next.next.next.next = new Node( 17 ); // Function Call System.out.println( "Absolute Difference between sum of alternate nodes: " + getAbsoluteDiff(head)); } } |
Python3
# Python code for the above approach: # Linked List Node class Node: def __init__( self , val): self .data = val self . next = None # Function to calculate absolute # difference between sum of alternate nodes def get_absolute_diff(head): sum1 = 0 sum2 = 0 flag = True while head is not None : # Based on flag decision made if flag: sum1 + = head.data else : sum2 + = head.data flag = not flag head = head. next return abs (sum1 - sum2) # Driver code if __name__ = = "__main__" : # Create a sample linked list: # 15 -> 16 -> 6 -> 7 -> 17 head = Node( 15 ) head. next = Node( 16 ) head. next . next = Node( 6 ) head. next . next . next = Node( 7 ) head. next . next . next . next = Node( 17 ) # Function Call print ( "Absolute Difference between sum of alternate nodes:" , get_absolute_diff(head)) |
C#
using System; // Linked List Node class Node { public int data; public Node next; public Node( int val) { data = val; next = null ; } } class Program { // Function to calculate absolute // difference between sum of alternate nodes static int GetAbsoluteDiff(Node head) { int sum1 = 0, sum2 = 0; bool flag = true ; while (head != null ) { // Based on flag decision made if (flag) { sum1 += head.data; } else { sum2 += head.data; } flag = !flag; head = head.next; } return Math.Abs(sum1 - sum2); } static void Main() { // Create a sample linked list: // 15 -> 16 -> 6 -> 7 -> 17 Node head = new Node(15); head.next = new Node(16); head.next.next = new Node(6); head.next.next.next = new Node(7); head.next.next.next.next = new Node(17); // Function Call Console.WriteLine( "Absolute Difference between sum of alternate nodes: " + GetAbsoluteDiff(head)); } } |
Javascript
// Linked List Node class Node { constructor(val) { this .data = val; this .next = null ; } } // Function to calculate absolute difference between sum of alternate nodes function getAbsoluteDiff(head) { let sum1 = 0, sum2 = 0; let flag = true ; while (head !== null ) { // Based on flag decision made if (flag) { sum1 += head.data; } else { sum2 += head.data; } flag = !flag; head = head.next; } return Math.abs(sum1 - sum2); } // Driver code function main() { // Create a sample linked list: // 15 -> 16 -> 6 -> 7 -> 17 const head = new Node(15); head.next = new Node(16); head.next.next = new Node(6); head.next.next.next = new Node(7); head.next.next.next.next = new Node(17); // Function Call console.log( "Absolute Difference between sum of alternate nodes: " + getAbsoluteDiff(head)); } // Run the program main(); |
Absolute Difference between sum of alternate nodes: 15
Time Complexity: O(n) (where, n = no. of nodes in linked list)
Auxiliary Space: O(1)