Find maximum pairwise sum in Linked List that are equidistant from front and back

Last Updated : 09 Mar, 2023

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 node struct 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 list void 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 list void 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 elements int 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 code int 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 approach class GFG{ // Structure of a node static 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 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);  System.out.print(pairSum(head)); } } // This code is contributed by 29AjayKumar

Python3

# Python code to implement above approach # Structure of a node class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next # Function to add node in linked list def 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 list def 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 elements def 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 sum head = 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# code to implement above approach using 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 node class ListNode {  constructor(x = null, next = null) {  this.val = x;  this.next = next;  } }; // Function to add node in linked list function 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 list function 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 elements function 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 code let 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