Find maximum absolute difference between weights of adjacent nodes in Linked list
Given a linked list with weights, the task is to find the maximum absolute difference between any two weights of nodes that are adjacent in the list.
Examples:
Input: 2 (4) -> 5 (8) -> 6 (1) -> 4 (3) -> 7 (2) -> NULL
Output: 7
Explanation: The maximum absolute difference between any two weights of nodes that are adjacent in the list is 7 (8 – 1) between nodes 5 and 6.Input: 4 (1) -> 8 (7) -> 2 (2) -> 6 (4) -> NULL
Output: 6
Explanation: The maximum difference between any two weights of nodes that are adjacent in the list is 6 (1 – 7) between nodes 4 and 8.
Approach: To solve the problem follow the below idea:
Traverse the Linked List and take the difference of adjacent elements in the list.
Here are the steps of the above approach:
- First, we define a function max_adjacent_diff to find the maximum absolute difference between any two adjacent nodes in the Linked list. The function takes the head of the list as input and returns an integer representing the maximum difference.
- Check if the list is empty or contains only one node. If so, we return 0 because there are no adjacent nodes to compare.
- Then we initialize a variable max_diff to hold the maximum difference seen so far to the absolute difference between the weights of the first two nodes in the list.
- Define a pointer curr to point to the second node in the list, as we have already compared the weights of the first two nodes.
- Then we iterate through the list, comparing the weight of each node with the weight of its next node. If the absolute difference between the weights of the two nodes is greater than the maximum difference seen so far, we update the maximum difference to the new difference.
- Once we have iterated through the entire list, we return the maximum absolute difference.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Define a struct to represent a node // in the linked list struct Node { int val; // Weight (or any other relevant data) // stored in the node int weight; // Pointer to the next node in the // linked list Node* next; }; // Function to insert a node at // the end of a linked list void push(Node** head, int val, int weight) { // Create a new node Node* new_node = new Node; // Set the value of the new node new_node->val = val; // Set the weight of the new node new_node->weight = weight; // Initialize the next pointer of the new node as // nullptr new_node->next = nullptr; if (*head == nullptr) { // If the linked list is empty, make // the new nodethe head of the // linked list *head = new_node; return ; } // Initialize a pointer to the last node Node* last = *head; // Traverse the linked list to // find the last node while (last->next != nullptr) { last = last->next; } // Make the new node the next // node of the last node last->next = new_node; } // Function to find the maximum difference // between weightsof adjacent nodes // in the linked list int max_adjacent_diff(Node* head) { if (!head || !head->next) { // If the list is empty or has only // one node, return 0 return 0; } // Initialize max_diff with // the difference between the // first two nodes int max_diff = abs (head->weight - head->next->weight); // Initialize a pointer to the // second node Node* curr = head->next; // Traverse the linked list and update // max_diff if a greater difference is found while (curr->next) { int diff = abs (curr->weight - curr->next->weight); if (diff > max_diff) { max_diff = diff; } curr = curr->next; } // Return the maximum difference return max_diff; } // Driver code int main() { // Create a linked list Node* head = nullptr; push(&head, 2, 4); push(&head, 5, 8); push(&head, 6, 1); push(&head, 4, 3); push(&head, 7, 2); // Function Call int max_diff = max_adjacent_diff(head); cout << "Maximum difference between weights of " "adjacent nodes: " << max_diff << endl; return 0; } |
Java
class Node { int val; int weight; Node next; Node( int val, int weight) { this .val = val; this .weight = weight; this .next = null ; } } class Main { // Function to insert a node at the end of a linked list static Node push(Node head, int val, int weight) { Node newNode = new Node(val, weight); if (head == null ) { // If the linked list is empty, make the new node the head head = newNode; return head; } Node last = head; while (last.next != null ) { last = last.next; } // Make the new node the next node of the last node last.next = newNode; return head; } // Function to find the maximum difference between weights of adjacent nodes in the linked list static int maxAdjacentDiff(Node head) { if (head == null || head.next == null ) { // If the list is empty or has only one node, return 0 return 0 ; } int maxDiff = Math.abs(head.weight - head.next.weight); Node curr = head.next; while (curr.next != null ) { int diff = Math.abs(curr.weight - curr.next.weight); if (diff > maxDiff) { maxDiff = diff; } curr = curr.next; } return maxDiff; } public static void main(String[] args) { // Create a linked list Node head = null ; head = push(head, 2 , 4 ); head = push(head, 5 , 8 ); head = push(head, 6 , 1 ); head = push(head, 4 , 3 ); head = push(head, 7 , 2 ); // Function Call int maxDiff = maxAdjacentDiff(head); System.out.println( "Maximum difference between weights of adjacent nodes: " + maxDiff); } } |
Python
# code contributed by Flutterfly # Define a class to represent a node in the linked list class Node: def __init__( self , val, weight): self .val = val self .weight = weight self . next = None # Function to insert a node at the end of a linked list def push(head, val, weight): new_node = Node(val, weight) if head is None : # If the linked list is empty, make the new node # the head of the linked list head = new_node return head last = head while last. next : last = last. next # Make the new node the next node of the last node last. next = new_node return head # Function to find the maximum difference between weights of adjacent nodes in the linked list def max_adjacent_diff(head): if not head or not head. next : # If the list is empty or has only one node, return 0 return 0 max_diff = abs (head.weight - head. next .weight) curr = head. next while curr. next : diff = abs (curr.weight - curr. next .weight) if diff > max_diff: max_diff = diff curr = curr. next return max_diff if __name__ = = "__main__" : # Create a linked list head = None head = push(head, 2 , 4 ) head = push(head, 5 , 8 ) head = push(head, 6 , 1 ) head = push(head, 4 , 3 ) head = push(head, 7 , 2 ) # Function Call max_diff = max_adjacent_diff(head) print ( "Maximum difference between weights of adjacent nodes:" , max_diff) |
C#
using System; // Define a class to represent a node in the linked list class Node { public int val; public int weight; public Node next; public Node( int val, int weight) { this .val = val; this .weight = weight; this .next = null ; } } class Program { // Function to insert a node at the end of a linked list static Node Push(Node head, int val, int weight) { Node newNode = new Node(val, weight); if (head == null ) { // If the linked list is empty, make the new node the head head = newNode; return head; } Node last = head; while (last.next != null ) { last = last.next; } // Make the new node the next node of the last node last.next = newNode; return head; } // Function to find the maximum difference between weights of adjacent nodes in the linked list static int MaxAdjacentDiff(Node head) { if (head == null || head.next == null ) { // If the list is empty or has only one node, return 0 return 0; } int maxDiff = Math.Abs(head.weight - head.next.weight); Node curr = head.next; while (curr.next != null ) { int diff = Math.Abs(curr.weight - curr.next.weight); if (diff > maxDiff) { maxDiff = diff; } curr = curr.next; } return maxDiff; } static void Main() { // Create a linked list Node head = null ; head = Push(head, 2, 4); head = Push(head, 5, 8); head = Push(head, 6, 1); head = Push(head, 4, 3); head = Push(head, 7, 2); // Function Call int maxDiff = MaxAdjacentDiff(head); Console.WriteLine( "Maximum difference between weights of adjacent nodes: " + maxDiff); } } |
Javascript
// JavaScript code for the above approach: // Define a class to represent a node // in the linked list class Node { constructor(val, weight) { this .val = val; // Weight (or any other relevant data) // stored in the node this .weight = weight; // Pointer to the next node in the // linked list this .next = null ; } } // Function to insert a node at //the end of a linked list function push(head, val, weight) { // Create a new node // Set the value of the new node // Set the weight of the new node const new_node = new Node(val, weight); if (head === null ) { // If the linked list is empty, make // the new nodethe head of the // linked list head = new_node; return head; } // Initialize a pointer to the last node let last = head; // Traverse the linked list to // find the last node while (last.next !== null ) { last = last.next; } // Make the new node the next // node of the last node last.next = new_node; return head; } // Function to find the maximum difference // between weights of adjacent nodes // in the linked list function maxAdjacentDiff(head) { if (!head || !head.next) { // If the list is empty or has only // one node, return 0 return 0; } // Initialize max_diff with // the difference between the // first two nodes let maxDiff = Math.abs(head.weight - head.next.weight); // Initialize a pointer to the // second node let curr = head.next; // Traverse the linked list and update // max_diff if a greater difference is found while (curr.next) { const diff = Math.abs(curr.weight - curr.next.weight); if (diff > maxDiff) { maxDiff = diff; } curr = curr.next; } // Return the maximum difference return maxDiff; } // Driver code // Create a linked list let head = null ; head = push(head, 2, 4); head = push(head, 5, 8); head = push(head, 6, 1); head = push(head, 4, 3); head = push(head, 7, 2); // Function Call const maxDiff = maxAdjacentDiff(head); console.log(`Maximum difference between weights of adjacent nodes: ${maxDiff}`); |
Maximum difference between weights of adjacent nodes: 7
Time Complexity: O(n), where n is the number of nodes in the linked list.
Auxiliary Space: O(1), because we use a constant amount of extra space regardless of the size of the linked list.