Maximum Twin Sum of a Linked List

Problem Description

Welcome to the world of linked lists, where nodes are like your friends at a party—some are just there to fill space, while others are the life of the party! The problem at hand is the Maximum Twin Sum of a Linked List. Imagine you have a list of numbers, and you want to find the maximum sum of pairs of numbers that are symmetrically positioned in the list.

Think of it like this: you and your twin (if you have one) are at a buffet. You both grab a plate and start loading it up with food. The goal? To see who can carry the most delicious food back to the table without dropping anything! In this case, the “delicious food” is the values in your linked list, and the “table” is where you calculate the maximum twin sum.

Code Solution


class Solution {
  public int pairSum(ListNode head) {
    int ans = 0;
    ListNode slow = head;
    ListNode fast = head;

    // `slow` points to the start of the second half.
    while (fast != null && fast.next != null) {
      slow = slow.next;
      fast = fast.next.next;
    }

    // `tail` points to the end of the reversed second half.
    ListNode tail = reverseList(slow);

    while (tail != null) {
      ans = Math.max(ans, head.val + tail.val);
      head = head.next;
      tail = tail.next;
    }

    return ans;
  }

  private ListNode reverseList(ListNode head) {
    ListNode prev = null;
    while (head != null) {
      ListNode next = head.next;
      head.next = prev;
      prev = head;
      head = next;
    }
    return prev;
  }
}

Approach Explanation

The solution involves a two-pointer technique. We use a slow pointer to find the midpoint of the linked list and a fast pointer to traverse the list at double speed. Once we reach the midpoint, we reverse the second half of the list. Then, we calculate the maximum twin sum by pairing the values from the first half and the reversed second half of the list.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n)
Space Complexity	O(1)

Real-World Example

Imagine you and your twin are competing in a food-eating contest. You both have to eat from opposite ends of a long table filled with delicious dishes. The goal is to see who can eat the most food without dropping any. The maximum twin sum is like calculating the total weight of food you both managed to carry back to the table. The heavier the food, the better the score!