LeetCode 2130 - Maximum Twin Sum of a Linked List

LeetCode Problem 2130

Difficulty: 🟡 Medium
Topics: Linked List, Two Pointers, Stack

Solution

Problem Understanding

The problem gives us a singly linked list with an even number of nodes. For every node at index i, there is a corresponding twin node at index n - 1 - i, where n is the total number of nodes in the list.

We define the twin sum as:

• node[i].val + node[n - 1 - i].val

Our task is to compute the maximum twin sum among all valid twin pairs.

For example, in the list:

[5,4,2,1]

The pairs are:

• 5 + 1 = 6
• 4 + 2 = 6

So the answer is 6.

The important detail is that the list is singly linked. Unlike arrays, we cannot directly access the last element or move backward efficiently. This restriction is what makes the problem interesting.

The constraints are large:

• Up to 10^5 nodes
• Node values up to 10^5

Because of this, any solution worse than linear or near-linear time may be too slow. We also need to think carefully about memory usage.

The problem guarantees:

• The list length is always even
• There are at least 2 nodes
• Every node contains a positive integer

These guarantees simplify the implementation because we never need to handle odd-length lists or empty lists.

Several edge cases are important:

• A list with only two nodes
• All twin sums being equal
• Very large node values
• Large lists where inefficient approaches become too slow
• Cases where the maximum twin sum appears in the middle rather than at the ends

Approaches

Brute Force Approach

The most direct idea is to first copy all linked list values into an array.

Once we have the array, accessing twin nodes becomes easy because arrays support random indexing. For every index i in the first half of the array, we compute:

values[i] + values[n - 1 - i]

We keep track of the maximum sum encountered.

This approach is straightforward and works correctly because the array preserves the original order of the linked list nodes.

However, although this solution is already acceptable for the problem constraints, it uses additional memory proportional to the size of the list.

A truly naive brute force approach without converting to an array would repeatedly scan the linked list to find the matching twin node for every position. That would require nested traversals and would result in quadratic time complexity, which is too slow for 10^5 nodes.

Optimal Approach

The key insight is that we only need to compare nodes from opposite ends of the list.

Since singly linked lists cannot move backward, we can solve this by reversing the second half of the linked list in place.

The high-level idea is:

1. Use slow and fast pointers to find the middle of the list.
2. Reverse the second half.
3. Traverse both halves simultaneously.
4. Compute twin sums and track the maximum.

After reversal:

• The first half moves forward normally.
• The reversed second half now also moves forward in the order we need.

This transforms the problem into a simple linear comparison between two linked lists.

Because we reverse the list in place, we achieve constant extra space usage.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force with repeated scans	O(n²)	O(1)	Finds each twin by traversing repeatedly
Array-based approach	O(n)	O(n)	Simple and intuitive
Optimal	O(n)	O(1)	Reverses second half in place

Algorithm Walkthrough

Optimal In-Place Reversal Algorithm

1. Use two pointers, slow and fast, starting at the head.

Move:

• slow by one step
• fast by two steps

When fast reaches the end, slow will point to the start of the second half. 2. Reverse the second half of the linked list.

Use the standard linked list reversal technique:

• Track prev
• Store next_node
• Reverse pointers one by one

After reversal, the second half is now ordered from the end toward the middle. 3. Initialize two pointers:

• first_half at the original head
• second_half at the head of the reversed second half

4. Traverse both halves simultaneously.

At each step:

• Compute the twin sum
• Update the maximum sum
• Move both pointers forward

5. Return the maximum twin sum found.

Why it works

The slow and fast pointer technique guarantees that we split the list exactly in half because the list length is always even.

Reversing the second half aligns corresponding twin nodes in traversal order:

Original:
1 -> 2 -> 3 -> 4

Second half reversed:
4 -> 3

Now:

• 1 aligns with 4
• 2 aligns with 3

This exactly matches the twin relationship defined in the problem. Since every twin pair is examined once, and we track the maximum, the algorithm always produces the correct answer.

Python Solution

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

from typing import Optional

class Solution:
    def pairSum(self, head: Optional[ListNode]) -> int:
        slow = head
        fast = head

        # Find the middle of the list
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse the second half
        prev = None
        current = slow

        while current:
            next_node = current.next
            current.next = prev
            prev = current
            current = next_node

        # Compute maximum twin sum
        max_sum = 0
        first_half = head
        second_half = prev

        while second_half:
            twin_sum = first_half.val + second_half.val
            max_sum = max(max_sum, twin_sum)

            first_half = first_half.next
            second_half = second_half.next

        return max_sum

The implementation begins by locating the midpoint using the classic slow and fast pointer technique. Because the list length is guaranteed to be even, the slow pointer ends exactly at the beginning of the second half.

Next, the second half is reversed in place. The variables prev, current, and next_node are used to safely reverse pointer directions without losing access to the remaining nodes.

After reversal, the list structure allows twin nodes to be traversed simultaneously from left to right. One pointer starts from the original head, while another starts from the reversed second half.

Each iteration computes one twin sum and updates the running maximum.

The algorithm finishes after all twin pairs have been processed.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func pairSum(head *ListNode) int {
    slow := head
    fast := head

    // Find middle of the list
    for fast != nil && fast.Next != nil {
        slow = slow.Next
        fast = fast.Next.Next
    }

    // Reverse second half
    var prev *ListNode
    current := slow

    for current != nil {
        nextNode := current.Next
        current.Next = prev
        prev = current
        current = nextNode
    }

    // Compute maximum twin sum
    maxSum := 0
    firstHalf := head
    secondHalf := prev

    for secondHalf != nil {
        twinSum := firstHalf.Val + secondHalf.Val

        if twinSum > maxSum {
            maxSum = twinSum
        }

        firstHalf = firstHalf.Next
        secondHalf = secondHalf.Next
    }

    return maxSum
}

The Go implementation follows the same algorithmic structure as the Python solution.

One difference is pointer handling. In Go, linked list nodes are manipulated using explicit pointers, so reversing the list involves careful reassignment of Next references.

Go also does not provide a built-in max function for integers, so the maximum value is updated manually using an if statement.

Since node values are at most 10^5, integer overflow is not a concern for Go's standard int type.

Worked Examples

Example 1

Input:

[5,4,2,1]

Step 1: Find the middle

Slow	Fast
5	5
4	2
2	nil

slow now points to 2.

Step 2: Reverse second half

Original second half:

2 -> 1

Reversed:

1 -> 2

Step 3: Compare twin pairs

First Half Node	Second Half Node	Twin Sum	Max Sum
5	1	6	6
4	2	6	6

Final answer:

6

Example 2

Input:

[4,2,2,3]

Step 1: Find middle

slow ends at the third node (2).

Step 2: Reverse second half

Original:

2 -> 3

Reversed:

3 -> 2

Step 3: Compare pairs

First Half Node	Second Half Node	Twin Sum	Max Sum
4	3	7	7
2	2	4	7

Final answer:

7

Example 3

Input:

[1,100000]

Step 1: Find middle

slow points to 100000.

Step 2: Reverse second half

Single-node reversal remains:

100000

Step 3: Compare pairs

First Half Node	Second Half Node	Twin Sum	Max Sum
1	100000	100001	100001

Final answer:

100001

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited a constant number of times
Space	O(1)	Reversal is performed in place

The algorithm performs three linear traversals:

1. Finding the middle
2. Reversing the second half
3. Computing twin sums

Each traversal is proportional to the number of nodes, so the total time complexity remains linear.

No additional data structures proportional to input size are allocated, so the extra space complexity is constant.

Test Cases

# Helper utilities for testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build_list(values):
    dummy = ListNode()
    current = dummy

    for value in values:
        current.next = ListNode(value)
        current = current.next

    return dummy.next

solution = Solution()

# Example 1
assert solution.pairSum(build_list([5, 4, 2, 1])) == 6  # all twin sums equal

# Example 2
assert solution.pairSum(build_list([4, 2, 2, 3])) == 7  # maximum at outer pair

# Example 3
assert solution.pairSum(build_list([1, 100000])) == 100001  # minimum size list

# Larger symmetric case
assert solution.pairSum(build_list([1, 2, 3, 4, 5, 6])) == 7  # multiple equal sums

# Maximum appears in middle pair
assert solution.pairSum(build_list([1, 10, 20, 30])) == 40  # inner pair largest

# Repeated values
assert solution.pairSum(build_list([7, 7, 7, 7])) == 14  # identical nodes

# Increasing sequence
assert solution.pairSum(build_list([1, 2, 3, 4, 5, 6, 7, 8])) == 9  # consistent sums

# Large values
assert solution.pairSum(build_list([100000, 1, 1, 100000])) == 200000  # large twin sum

# Two identical nodes
assert solution.pairSum(build_list([42, 42])) == 84  # smallest even list

# Uneven distribution
assert solution.pairSum(build_list([9, 1, 8, 2, 7, 3])) == 12  # varied pair sums

Test Summary

Test	Why
[5,4,2,1]	Verifies basic functionality
[4,2,2,3]	Checks differing twin sums
[1,100000]	Validates minimum list size
[1,2,3,4,5,6]	Tests multiple equal sums
[1,10,20,30]	Ensures inner pair can be maximum
[7,7,7,7]	Tests repeated values
[1,2,3,4,5,6,7,8]	Larger even-length traversal
[100000,1,1,100000]	Validates large values
[42,42]	Simplest possible valid input
[9,1,8,2,7,3]	Mixed pair sums

Edge Cases

Minimum Size List

The smallest valid input contains exactly two nodes. In this case there is only one twin pair. Algorithms that assume at least four nodes may fail or incorrectly handle midpoint logic.

The implementation handles this naturally because the slow and fast pointer traversal still works correctly, and reversing a single-node second half is valid.

Large Node Values

Node values can be as large as 100000. If an implementation uses an inappropriate numeric type in some languages, overflow could become a concern.

The provided Python and Go implementations safely handle these values because the resulting sums remain well within supported integer ranges.

Maximum Twin Sum Not at the Ends

A common mistake is assuming the first and last nodes always produce the maximum twin sum.

For example:

[1,10,20,30]

Twin sums are:

1 + 30 = 31
10 + 20 = 30

In other cases, the inner pair may be larger. The implementation correctly evaluates every twin pair instead of relying on assumptions about ordering.

Reversal Pointer Bugs

Linked list reversal is error-prone because modifying pointers can accidentally disconnect nodes or create cycles.

The implementation avoids this by always storing next_node before changing current.next. This guarantees the remaining portion of the list is never lost during reversal.