Maximum Twin Sum of a Linked List: Reverse and Compare

Maximum Twin Sum of a Linked List is LeetCode 2130. You are given a linked list with an even number of nodes. The twist: every node has a "twin" on the opposite side of the list. Node i is paired with node n - 1 - i, and the twin sum is the sum of their values. Your job is to find the maximum twin sum across all pairs.

The problem

Given the head of a linked list with even length n, the twin of node i is node n - 1 - i (using 0-based indexing). The twin sum is defined as the sum of a node's value and its twin's value. Return the maximum twin sum of the linked list.

Example: head = [5, 4, 2, 1]. The twins are (5, 1) with sum 6 and (4, 2) with sum 6. The maximum twin sum is 6.

Why reverse the second half

You could solve this with an array or a stack. Copy all values into an array, then compare index i with index n - 1 - i. That works in O(n) time and O(n) space.

But there is a cleaner approach that uses O(1) extra space. The idea: reverse the second half of the linked list in place. Once reversed, the head of the second half lines up perfectly with the head of the first half. You can walk two pointers side by side, comparing twin sums as you go.

This "reverse the second half" technique is a classic linked list pattern. You will see it in Palindrome Linked List (LeetCode 234), Reorder List (LeetCode 143), and right here.

The approach

The solution breaks down into three phases:

1. Find the middle using fast and slow pointers. When fast reaches the end, slow sits at the start of the second half.
2. Reverse the second half of the list in place. The node that was at position n - 1 is now the head of the reversed portion.
3. Walk both halves simultaneously. One pointer starts at head (first half), the other starts at the head of the reversed second half. At each step, compute the sum and track the maximum.

Visual walkthrough

The key insight: after reversing, the first node of the reversed half was originally the last node of the list, which is the twin of the first node. So walking both halves in lockstep naturally pairs up twins.

The solution

def pairSum(head):
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    prev = None
    curr = slow
    while curr:
        curr.next, prev, curr = prev, curr, curr.next

    max_sum = 0
    first = head
    second = prev
    while second:
        max_sum = max(max_sum, first.val + second.val)
        first = first.next
        second = second.next

    return max_sum

Here is the breakdown:

1. Find the middle (lines 2-6). slow advances one node per iteration, fast advances two. When fast hits null or the last node, slow is at the midpoint. For a list of length 4, slow ends up at index 2.
2. Reverse the second half (lines 8-11). Starting from slow, reverse all remaining nodes. After this loop, prev points to what was the last node of the original list, which is now the head of the reversed second half.
3. Compare and find max (lines 13-18). Walk first from the original head and second from the reversed head. Each pair (first.val, second.val) is a twin pair. Track the maximum sum.

Complexity analysis

The building blocks

Find middle + reverse second half

This is a composite pattern that appears whenever you need to compare elements from opposite ends of a singly linked list without extra space. The idea is simple: you cannot traverse a singly linked list backwards, so you make the second half go forward by reversing it. Then you have two forward-only traversals that naturally pair up elements from opposite ends.

Finding the middle with fast/slow pointers is O(n). Reversing the second half is O(n). Walking both halves is O(n). Three passes, all linear, no extra data structures.

This same composite pattern appears in Palindrome Linked List (LeetCode 234), where you reverse the second half and compare it to the first half for equality. It also shows up in Reorder List (LeetCode 143), where you reverse the second half and interleave it with the first half.

Edge cases

• Two nodes. The only twin pair. Return the sum of both values.
• All equal values. Every twin sum is the same. Return that sum.
• Maximum at the ends. The first and last nodes form the max twin sum.
• Maximum in the middle. The two middle-adjacent nodes form the max twin sum.

From understanding to recall

This problem tests three separate skills: finding the middle of a linked list, reversing a linked list, and two-pointer traversal. If any of those is shaky, the whole solution breaks down. You might remember the overall strategy ("reverse the second half and compare") but forget how the reversal loop works, or mix up where slow ends up for even-length lists.

The fix is to practice each building block individually until it is automatic, then combine them. Once you can write the fast/slow midpoint finder and the in-place reversal without thinking, this problem becomes a matter of wiring them together.

Related posts

• Reverse Linked List - The foundational reversal technique used in this solution
• Palindrome Linked List - Uses the same reverse-second-half pattern to check symmetry
• Middle of the Linked List - Finding the midpoint with fast and slow pointers