Maximum Twin Sum of a Linked List — Fast/Slow + Reverse Second Half

Problem Statement#

LeetCode 2130 — Maximum Twin Sum of a Linked List Difficulty: Medium | Pattern: Fast/Slow Pointer + Reverse Second Half

In a linked list of even size n, the ith node (0-indexed) is the twin of the (n-1-i)th node. The twin sum is the sum of a node and its twin. Return the maximum twin sum of the linked list.

Constraints:

• Number of nodes: 2 <= n <= 10^5 (always even)
• 1 <= Node.val <= 10^5

Example 1:

Input:  [5, 4, 2, 1]
Output: 6
Explanation:
  node 0 (val=5) is twin of node 3 (val=1) -> sum = 6
  node 1 (val=4) is twin of node 2 (val=2) -> sum = 6
  Maximum twin sum = 6

Example 2:

Input:  [4, 2, 2, 3]
Output: 7
Explanation:
  node 0 (val=4) is twin of node 3 (val=3) -> sum = 7
  node 1 (val=2) is twin of node 2 (val=2) -> sum = 4
  Maximum twin sum = 7

Example 3:

Input:  [1, 100000]
Output: 100001

Why This Problem Matters#

This problem appears in the LeetCode 75 study plan — a curated set of essential problems for interview preparation — which means it is actively assigned as homework at companies like Amazon, Google, and Meta before technical screens.

The twin sum concept is a mirror-pairing problem: you need to compare index 0 with index n-1, index 1 with index n-2, and so on. In an array, this is trivial. In a linked list, there is no backward traversal and no random access — you must be creative.

The naive approach converts the list to an array in O(n) time and O(n) space, then computes twin sums. This is perfectly acceptable in an interview but misses the O(1) space optimization. The optimal approach — splitting the list at the midpoint, reversing the second half in-place, then walking both halves together — achieves O(n) time and O(1) space.

Interviewers use this problem to test whether you recognize that "reversing the second half" is the standard technique for comparing first and second halves of a linked list — the same pattern used in "Palindrome Linked List" (LC 234) and "Reorder List" (LC 143).

The Core Insight#

The key realization is: if you reverse the second half of the list, the "twin" of node i is now exactly opposite to node i as you walk from the start and the reversed end simultaneously.

Three-step algorithm:

1. Find the midpoint using fast and slow pointers. When fast reaches the end, slow is at the midpoint.
2. Reverse the second half starting from slow. Now the reversed half starts at the node that was last.
3. Walk both halves together, computing sums and tracking the maximum.

This produces O(n) time and O(1) space. Note: reversing in-place modifies the list structure, which is acceptable unless the problem explicitly forbids it. In an interview, always ask whether the list may be modified.

Visual Dry Run#

Input: [4, 2, 2, 3]

Step 1 — Find midpoint:

slow=4, fast=4
slow=2, fast=2  (fast moved 2 steps)
slow=2(mid), fast=3 (fast.next is null — stop)

Step 2 — Reverse second half from slow (node at index 2):

Before: 2 -> 3 -> null
After reversal: 3 -> 2 -> null    (prev = node(3))

Step 3 — Walk first half and reversed second half:

first = head = node(4)
second = prev = node(3)
 
Pair (4, 3): sum = 7  -> max = 7
Pair (2, 2): sum = 4  -> max = 7

Result: 7

Solution (Optimal)#

from typing import Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def pairSum(head: Optional[ListNode]) -> int:
    # Step 1: Find the midpoint using fast/slow pointers
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
 
    # Step 2: Reverse the second half in-place
    prev = None
    curr = slow
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    # prev is now the head of the reversed second half
 
    # Step 3: Walk both halves, compute max twin sum
    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

function pairSum(head) {
    // Step 1: Find midpoint
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
 
    // Step 2: Reverse second half in-place
    let prev = null;
    let curr = slow;
    while (curr) {
        const nxt = curr.next;
        curr.next = prev;
        prev = curr;
        curr = nxt;
    }
 
    // Step 3: Compute max twin sum
    let maxSum = 0;
    let first = head;
    let second = prev;
    while (second) {
        maxSum = Math.max(maxSum, first.val + second.val);
        first = first.next;
        second = second.next;
    }
 
    return maxSum;
}

Complexity:

Simpler alternative (O(n) space):

def pairSum(head):
    values = []
    while head:
        values.append(head.val)
        head = head.next
    n = len(values)
    return max(values[i] + values[n - 1 - i] for i in range(n // 2))

Common Mistakes#

1. Using the wrong stop condition for slow/fast: while fast and fast.next ensures fast stops at the last node for even-length lists, placing slow exactly at the start of the second half.
2. Reversing the wrong half: Always reverse the second half (starting from slow after the midpoint traversal). Reversing the first half works too but is more confusing to explain.
3. Using second.next instead of second in the while condition: Walk using second as the condition since the reversed half is shorter than or equal to the first half.
4. Forgetting that n is always even: The constraint guarantees this, so you do not need to handle odd-length lists for this specific problem.
5. Modifying the list without mentioning it: In an interview, explicitly state "I will reverse the second half in-place — is that acceptable?" This shows awareness of side effects.

Interview Tips#

• Start with the array approach: "The simple solution converts the list to an array in O(n) space. Can I do better?" Then present the O(1) space solution.
• Name the three steps: Find midpoint → Reverse second half → Compare pairs. Interviewers love structured explanations.
• Relate to Palindrome Linked List: "This uses the same technique as LC 234. I reverse the second half and compare from both ends."
• Mention the in-place modification: Always note that the list is structurally modified. If the interviewer cares, you can restore the list by reversing the second half again afterward.
• Trace the dry run: Walking through [4, 2, 2, 3] step by step takes 2 minutes and demonstrates correctness far better than verbal explanation alone.

Follow-up Questions#

1. How would you restore the original list? Reverse the second half again after computing the answer.
2. LeetCode 234 — Palindrome Linked List: Uses the exact same technique — reverse second half, compare with first half.
3. LeetCode 143 — Reorder List: Also splits at midpoint and reverses the second half before interleaving.
4. What if n could be odd? The twin sum concept only applies to even-length lists per the problem definition, but you should verify this with the interviewer.
5. Can you solve it without modifying the list? Yes, using a stack to store the second half. This is O(n) space but keeps the list intact.
6. What if you needed the pair that achieves the maximum, not just the sum? Track the indices when you find the new maximum.

Key Takeaways#

• The fast/slow pointer finds the midpoint in one pass; when fast is done, slow is at the start of the second half.
• Reversing the second half in-place converts the twin-pairing problem into a simple parallel walk from both ends.
• Three clean passes (find midpoint, reverse, compare) give O(n) time and O(1) space.
• This same three-step template solves LC 234 (Palindrome Linked List) and LC 143 (Reorder List).
• The simpler O(n) space solution (convert to array) is acceptable in an interview — present it first, then optimize.
• Always mention in-place modification to the interviewer — showing awareness of side effects is a sign of engineering maturity.