Maximum Twin Sum of a Linked List

Problem

You are given the head of a singly linked list with an even number of nodes, n. Pair up the nodes symmetrically from the two ends: the node at position i (0-indexed) is the twin of the node at position n - 1 - i. So the first node is twinned with the last, the second with the second-to-last, and so on — every node has exactly one twin.

The twin sum of a pair is the sum of the two twins’ values. Return the maximum twin sum over all pairs in the list.

Examples

• Input: head = [5, 4, 2, 1] → Output: 6 Pairs are (5,1) and (4,2); both sum to 6, so the max is 6.
• Input: head = [4, 2, 2, 3] → Output: 7 Pairs are (4,3)=7 and (2,2)=4; the max is 7.
• Input: head = [1, 100000] → Output: 100001 Only one pair exists: (1, 100000).

Constraints

• The number of nodes n is even and 2 <= n <= 10^5.
• 1 <= Node.val <= 10^5.

The linear size means anything quadratic (re-walking the list for every node) is too slow; aim for O(n) time.

Think about it first

TL;DR

Find the middle, reverse the second half, sweep both halves in lockstep — O(n) time, O(1) space.

Approach 1 — Brute force: walk to each twin

For each node at position i, walk from the head n - 1 - i steps to reach its twin, and take the max of the sums.

# 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:
        n = 0
        node = head
        while node:
            n += 1
            node = node.next
        best = 0
        node = head
        for i in range(n // 2):
            twin = head
            for _ in range(n - 1 - i):
                twin = twin.next
            best = max(best, node.val + twin.val)
            node = node.next
        return best

Time O(n^2), space O(1). With n up to 10^5, ~10^10 pointer hops is far past any time limit.

Approach 2 — Copy values into an array

Insight: twins are defined by positions, and positions are trivial with random access. Dump the values into a Python list and pair index i with index n - 1 - i directly.

# 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:
        vals: List[int] = []
        node = head
        while node:
            vals.append(node.val)
            node = node.next
        n = len(vals)
        return max(vals[i] + vals[n - 1 - i] for i in range(n // 2))

Walkthrough on [4, 2, 2, 3]: vals = [4, 2, 2, 3], n = 4. i=0 pairs 4+3=7; i=1 pairs 2+2=4. Max is 7.

Time O(n), space O(n) for the copied values.

Approach 3 — Middle + reverse second half (optimal)

Insight: the twin pairs are (first half, second half reversed) aligned position by position. So: locate the middle with the classic slow/fast pointer technique (fast moves two steps per slow’s one, so when fast reaches the end, slow is at the midpoint), reverse the second half in place, then walk the two halves together.

# 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:
        # 1. slow/fast to find the start of the second half
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # 2. reverse the second half in place
        prev = None
        while slow:
            nxt = slow.next
            slow.next = prev
            prev = slow
            slow = nxt

        # 3. lockstep sweep: prev heads the reversed second half
        best = 0
        first, second = head, prev
        while second:
            best = max(best, first.val + second.val)
            first = first.next
            second = second.next
        return best

Walkthrough on [5, 4, 2, 1]:

1. slow/fast: slow ends at the node 2 (index 2), the start of the second half.
2. Reversing 2 → 1 yields 1 → 2; prev points at 1.
3. Lockstep: (5,1) → 6, then (4,2) → 6. Answer: 6. (Note first still runs into the old, now-severed half — but the loop is bounded by second, which is exactly n/2 nodes.)

Time O(n) (three linear passes), space O(1).

Common pitfalls

• Bounding the final loop by first instead of second — after the reversal the first half’s last node still points into the second half in some variants, so always iterate exactly n/2 steps via second.
• Off-by-one in the slow/fast loop: with while fast and fast.next, slow lands on node n/2 for even n, which is exactly the start of the second half here.
• Forgetting the list is guaranteed even-length and adding dead odd-length handling that obscures the logic.
• Initializing best = head.val or similar instead of 0 — harmless here since values are positive, but the clean invariant is “max over pairs seen so far”, starting empty.

Pattern takeaway

“Fold the list in half” problems (palindrome check, twin sums, reorder) all reduce to the same three-step kit: slow/fast to find the middle, in-place reversal of one half, lockstep walk of the two halves. Learn the kit once and these become assembly, not invention.