Maximum Twin Sum of a Linked List
Return the largest sum of a node and its twin, the node the same distance from the other end, by reversing the back half of the list and walking both halves at once.
Problem Understanding
Maximum Twin Sum of a Linked List (LeetCode 2130): in a linked list of even length n, node i and node n - 1 - i (0-indexed) are twins. The twin sum is the sum of their values. Given the head, return the maximum twin sum.
Examples: [5, 4, 2, 1] → 6 (5 + 1 and 4 + 2); [4, 2, 2, 3] → 7 (4 + 3); [1, 100000] → 100001.
The Intuition: Fold the List in Half
Picture folding the list at the middle so the back half lies on top of the front half, end to start. Each node then sits on its twin.
- Find the fold. Slow and fast pointers, as in Middle of the Linked List, leave slow on the first node of the back half.
- Turn the back half around. Reverse it in place, as in Reverse Linked List.
- Walk the halves together. head and the new back-half head now meet the twins pair by pair.
Palindrome Linked List uses the same fold to compare twins instead of adding them.
Interactive Walkthrough
4 NODES · TWIN OF i IS 3 − i
BOTH AT HEAD
slow fast
0
→
1
→
2
→
3
→ NULL
Twin sum
:
Best
0
Answer
:
slow and fast both start at head
Next
slow moves 1 to 2; fast moves 2 to 2
head
The nodes stay in input order. As the back half is reversed its arrows flip to ←. Then the two twins being added are highlighted, one moving right from the head and one moving left from the tail. Try Six nodes, where the best pair is not the outermost one.
Dry Run Table
Input: [4, 2, 2, 3]. slow and fast stop with slow on index 2. After reversing, the back half reads 3 → 2.
| Pair | head | prev | Sum | best |
|---|---|---|---|---|
| 1 | 4 (index 0) | 3 (index 3) | 7 | 7 |
| 2 | 2 (index 1) | 2 (index 2) | 4 | 7 |
Answer: 7.
The Solution Template
Three loops: slow and fast to the middle, an in-place reversal of the back half, and a joint walk that keeps the best sum.
Maximum Twin Sum of a Linked List Code
1var pairSum = function(head) {2 let slow = head, fast = head;3 while (fast && fast.next) {4 slow = slow.next;5 fast = fast.next.next;6 }7 let prev = null;8 while (slow) {9 const next = slow.next;10 slow.next = prev;11 prev = slow;12 slow = next;13 }14 let best = 0;15 while (prev) {16 best = Math.max(best, head.val + prev.val);17 head = head.next;18 prev = prev.next;19 }20 return best;21};
Edge Cases & Common Mistakes
- Two nodes: one pair, so the answer is their sum.
- Stopping the last loop on head instead of prev: the front half still points into the back half, so walk until prev, the shorter side, runs out.
- Reversing from the wrong node: with an even length, slow lands on the first node of the back half; reverse from there, not from slow.next.
- Python tuple assignment order:
slow.next, prev, slow = prev, slow, slow.nextis safe because the right side is evaluated first. - Mutating the input: reverse the back half again afterwards if the caller needs the list intact.
Summary
Find the middle with slow and fast pointers, reverse the back half, then walk head and the reversed half together and keep the largest sum. O(n) time, O(1) extra space.
More practice: DSA interview questions with answers · patterns cheat sheet