Maximum Twin Sum of a Linked List – LeetCode75 Python Solution Explained

The Maximum Twin Sum of a Linked List problem (LeetCode75) is a popular linked list challenge that tests your ability to manipulate lists, use indexing smartly and compute pairwise sums efficiently. It’s commonly asked in coding interviews because it strengthens your problem-solving skills in array manipulation and linked list traversal.

In this blog, we’ll cover the problem statement, understand it step by step, walk through examples, provide a complete Python solution, explain the logic in detail, and analyze complexities. Finally, we’ll look at real-world applications of the twin sum pattern.

Problem Statement

You are given the head of a singly linked list of even length. The list nodes can be paired as follows:

The i-th node from the start and the i-th node from the end are considered a twin pair.
The twin sum is the sum of their values.

Your task is to return the maximum twin sum of the linked list.

Example:

Input: head = [5, 4, 2, 1]
Output: 6
Explanation: The pairs are (5,1) and (4,2) → sums = 6, 6 → maximum = 6.

Understanding the Problem

The concept is straightforward:

We need to form pairs such that the first node is paired with the last, the second with the second last and so on.
Compute the twin sum for each pair.
Find the maximum twin sum.

The challenge lies in efficiently traversing the list and pairing elements without losing track of indices.

Examples

Example 1

Input: [5, 4, 2, 1]
Output: 6
Explanation: Pairs (5+1=6) and (4+2=6) → max = 6.

Example 2

Input: [4, 2, 2, 3]
Output: 7
Explanation: Pairs (4+3=7) and (2+2=4) → max = 7.

Example 3

Input: [1, 100000]
Output: 100001
Explanation: Only one pair (1+100000=100001).

Complete Python Solution

from typing import Optional

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        values = []
        while head:
            values.append(head.val)
            head = head.next

        n = len(values)
        max_twin_sum = 0

        for i in range(n // 2):
            twin_sum = values[i] + values[n - 1 - i]
            max_twin_sum = max(max_twin_sum, twin_sum)

        return max_twin_sum

Step-by-Step Explanation

Step 1: Traverse the Linked List

We first convert the linked list into a list of values for easier index access.

values = []
while head:
    values.append(head.val)
    head = head.next

Step 2: Compute Twin Sums

Using the formula (i + (n-1-i)), we pair the first with the last, second with the second last and so on.

for i in range(n // 2):
    twin_sum = values[i] + values[n - 1 - i]

Step 3: Track the Maximum Twin Sum

We update the maximum as we go.

max_twin_sum = max(max_twin_sum, twin_sum)

Step 4: Return the Result

Finally, return the highest twin sum found.

return max_twin_sum

Time and Space Complexity

Time Complexity: O(n) – One pass to build the array, another to compute twin sums.
Space Complexity: O(n) – Storing linked list values in an array.

Edge Cases

List with only two nodes → Single pair, direct sum.
Very large values → Ensure integer handling works correctly.
Symmetric lists → All twin sums equal.

Real-World Applications

The twin sum pattern mirrors many real-world scenarios:

Data pairing problems where values must be combined from opposite ends (e.g. merging stock data, sales reports).
Load balancing by pairing large and small tasks for optimized distribution.
Signal processing where data is analyzed in mirrored segments.
Symmetry detection in algorithms that require checking balanced values.

Conclusion

The Maximum Twin Sum of a Linked List (LeetCode75) problem is an excellent exercise in linked list traversal, array manipulation and problem-solving with indices. By extracting values and pairing them smartly, we can compute the maximum twin sum in linear time.

Practicing this problem not only improves your linked list skills but also prepares you for coding interviews where symmetry, pairing and efficient traversal techniques are tested. It’s a powerful pattern that has practical applications in data analysis, load distribution and algorithm design.