Given a linked list lis of length N, where N is even. The task is to maximize the sum of two equidistant nodes from the front and back ends of the given linked list.
Note: Two nodes (i and j) are equidistant from both ends if the distance of ith node from front is same as distance of jth node from back.
Examples:
Input: lis = {5, 4, 2, 1}
Output: 6
Explanation: The nodes with pairs present in this linked list are:
Node 0 and node 3 are equidistant having a sum of 5 + 1 = 6.
Node 1 and node 2 are equidistant having a sum of 4 + 2 = 6.
Thus, the maximum sum of equidistant nodes of the linked list is max(6, 6) = 6.Input: lis = {4, 2, 2, 3}
Output: 7
Explanation: The nodes with pairs present in this linked list are:
Node 0 and node 3 are equidistant having a sum of 4 + 3 = 7.
Node 1 and node 2 are equidistant having a sum of 2 + 2 = 4.
Thus, the maximum sum of equidistant nodes of the linked list is max(7, 4) = 7.
Approach: The solution is based on dividing the linked list into two equal halves and then using two pointer approach. Follow the steps mentioned below to solve the problem:
- Get mid and separate the linked list into two parts.
- Reverse the second part, for traversing it in the forward direction.
- Traverse in both parts and get the maximum sum.
- Recover the Linked List Again, by connecting the parts again, for good practice.
Below is the implementation of the above approach.
C++
// C++ code to implement above approach#include <bits/stdc++.h>using namespace std;// Structure of a nodestruct ListNode { int val; ListNode* next; ListNode() : val(0), next(nullptr) { } ListNode(int x) : val(x), next(nullptr) { } ListNode(int x, ListNode* next) : val(x), next(next) { }};// Function to add node in linked listvoid push(struct ListNode** head_ref, int new_data){ // Allocate node struct ListNode* new_node = new ListNode; // Put in the data new_node->val = new_data; // Link the old list of the new node new_node->next = (*head_ref); // Move the head to point the new node (*head_ref) = new_node;}// Function for reversing the linked listvoid reverse(ListNode** head){ ListNode *curr = *head, *prev = 0, *nxt; while (curr) nxt = curr->next, curr->next = prev, prev = curr, curr = nxt; *head = prev;}// Function to find the maximum sum// of equidistant elementsint pairSum(ListNode* head){ // Get mid and separate // the linked list into two parts ListNode *prev = 0, *slow = head, *fast = head; // Find mid while (fast and fast->next) prev = slow, slow = slow->next, fast = fast->next->next; // Separate them prev->next = 0; // Reverse the second part, // for traversing it // in forward direction reverse(&slow); // Traverse in both parts and // get the maximum sum int sum = 0; ListNode *ptr1 = head, *ptr2 = slow; while (ptr1) sum = max(sum, (ptr1->val + ptr2->val)), ptr1 = ptr1->next, ptr2 = ptr2->next; // Recover the Linked List again, by // connection the parts again reverse(&slow); prev->next = slow; // Return sum return sum;}// Driver codeint main(){ struct ListNode* head = NULL; push(&head, 4); push(&head, 2); push(&head, 2); push(&head, 3); cout << pairSum(head); return 0;} |
Java
// Java code to implement above approachclass GFG{// Structure of a nodestatic class ListNode { int val; ListNode next; ListNode() { this(0); } ListNode(int x) { this.val = x; this.next = null; } ListNode(int x, ListNode next) { this.val = x; this.next = next; }};// Function to add node in linked liststatic ListNode push(ListNode head_ref, int new_data){ // Allocate node ListNode new_node = new ListNode(); // Put in the data new_node.val = new_data; // Link the old list of the new node new_node.next = head_ref; // Move the head to point the new node head_ref = new_node; return head_ref;}// Function for reversing the linked liststatic ListNode reverse(ListNode head){ ListNode curr = head, prev = new ListNode(), nxt=new ListNode(); while (curr.next!=null) { nxt = curr.next; curr.next = prev; prev = curr; curr = nxt; } head = prev; return head;}// Function to find the maximum sum// of equidistant elementsstatic int pairSum(ListNode head){ // Get mid and separate // the linked list into two parts ListNode prev = new ListNode(), slow = head, fast = head; // Find mid while (fast!=null && fast.next!=null) { prev = slow; slow = slow.next; fast = fast.next.next; } // Separate them prev.next = new ListNode(); // Reverse the second part, // for traversing it // in forward direction slow = reverse(slow); // Traverse in both parts and // get the maximum sum int sum = 0; ListNode ptr1 = head, ptr2 = slow; while (ptr1!=null) { sum = Math.max(sum, (ptr1.val + ptr2.val)); ptr1 = ptr1.next; ptr2 = ptr2.next; } // Recover the Linked List again, by // connection the parts again slow = reverse(slow); prev.next = slow; // Return sum return sum;}// Driver codepublic static void main(String[] args){ ListNode head = new ListNode(); head = push(head, 4); head = push(head, 2); head = push(head, 2); head = push(head, 3); System.out.print(pairSum(head));}}// This code is contributed by 29AjayKumar |
Python3
# Python code to implement above approach# Structure of a nodeclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next# Function to add node in linked listdef push(head_ref, new_data): # Allocate node new_node = ListNode(new_data) # Link the old list of the new node new_node.next = head_ref # Move the head to point the new node head_ref = new_node return head_ref# Function for reversing the linked listdef reverse(head): curr = head prev = None nxt = None while curr.next is not None: nxt = curr.next curr.next = prev prev = curr curr = nxt head = prev return head# Function to find the maximum sum# of equidistant elementsdef pairSum(head): # Get mid and separate # the linked list into two parts prev = None slow = head fast = head # Find mid while fast is not None and fast.next is not None: prev = slow slow = slow.next fast = fast.next.next # Separate them prev.next = None # Reverse the second part, # for traversing it # in forward direction slow = reverse(slow) # Traverse in both parts and # get the maximum sum sum = 0 ptr1 = head ptr2 = slow while ptr1 is not None: sum = max(sum, (ptr1.val + ptr2.val)) ptr1 = ptr1.next ptr2 = ptr2.next # Recover the Linked List again, by # connection the parts again slow = reverse(slow) prev.next = slow # Return sum return sumhead = ListNode()head = push(head, 4)head = push(head, 2)head = push(head, 2)head = push(head, 3)print(pairSum(head))# This code is contributed by lokesh. |
C#
// C# code to implement above approachusing System;public class GFG{ // Structure of a node class ListNode { public int val; public ListNode next; public ListNode() { new ListNode(0); } public ListNode(int x) { this.val = x; this.next = null; } public ListNode(int x, ListNode next) { this.val = x; this.next = next; } }; // Function to add node in linked list static ListNode push(ListNode head_ref, int new_data) { // Allocate node ListNode new_node = new ListNode(); // Put in the data new_node.val = new_data; // Link the old list of the new node new_node.next = head_ref; // Move the head to point the new node head_ref = new_node; return head_ref; } // Function for reversing the linked list static ListNode reverse(ListNode head) { ListNode curr = head, prev = new ListNode(), nxt=new ListNode(); while (curr.next!=null) { nxt = curr.next; curr.next = prev; prev = curr; curr = nxt; } head = prev; return head; } // Function to find the maximum sum // of equidistant elements static int pairSum(ListNode head) { // Get mid and separate // the linked list into two parts ListNode prev = new ListNode(), slow = head, fast = head; // Find mid while (fast!=null && fast.next!=null) { prev = slow; slow = slow.next; fast = fast.next.next; } // Separate them prev.next = new ListNode(); // Reverse the second part, // for traversing it // in forward direction slow = reverse(slow); // Traverse in both parts and // get the maximum sum int sum = 0; ListNode ptr1 = head, ptr2 = slow; while (ptr1!=null) { sum = Math.Max(sum, (ptr1.val + ptr2.val)); ptr1 = ptr1.next; ptr2 = ptr2.next; } // Recover the Linked List again, by // connection the parts again slow = reverse(slow); prev.next = slow; // Return sum return sum; } // Driver code public static void Main(String[] args) { ListNode head = new ListNode(); head = push(head, 4); head = push(head, 2); head = push(head, 2); head = push(head, 3); Console.Write(pairSum(head)); }}// This code is contributed by shikhasingrajput |
Javascript
// Javascript code to implement above approach// Structure of a nodeclass ListNode { constructor(x = null, next = null) { this.val = x; this.next = next; }};// Function to add node in linked listfunction push(head_ref, new_data) { // Allocate node let new_node = new ListNode(); // Put in the data new_node.val = new_data; // Link the old list of the new node new_node.next = head_ref; // Move the head to point the new node head_ref = new_node; return head_ref;}// Function for reversing the linked listfunction reverse(head) { let curr = head, prev = new ListNode(), nxt = new ListNode(); while (curr.next != null) { nxt = curr.next; curr.next = prev; prev = curr; curr = nxt; } head = prev; return head;}// Function to find the maximum sum// of equidistant elementsfunction pairSum(head) { // Get mid and separate // the linked list into two parts let prev = new ListNode(), slow = head, fast = head; // Find mid while (fast != null && fast.next != null) { prev = slow; slow = slow.next; fast = fast.next.next; } // Separate them prev.next = new ListNode(); // Reverse the second part, // for traversing it // in forward direction slow = reverse(slow); // Traverse in both parts and // get the maximum sum let sum = 0; let ptr1 = head, ptr2 = slow; while (ptr1 != null) { sum = Math.max(sum, (ptr1.val + ptr2.val)); ptr1 = ptr1.next; ptr2 = ptr2.next; } // Recover the Linked List again, by // connection the parts again slow = reverse(slow); prev.next = slow; // Return sum return sum;}// Driver codelet head = new ListNode();head = push(head, 4);head = push(head, 2);head = push(head, 2);head = push(head, 3);console.log(pairSum(head));// This code is contributed by Saurabh Jaiswal |
Output
7
Time Complexity: O(N)
Auxiliary Space: O(1)
