Max Twin Sum Linked List LeetCode 2130

LeetCode 2130 — Maximum Twin Sum of a Linked List — gives you a singly linked list with an even number of nodes. The twin of node i (0-indexed) is defined as node (n-1-i), where n is the total number of nodes. For example, in a 6-node list the twin pairs are (0,5), (1,4), and (2,3). Your task is to return the maximum twin sum, where twin sum = node[i].val + node[n-1-i].val.

The pairing is symmetric and mirrors both ends toward the center, similar to how palindrome checking compares characters from both ends. Every node in the first half has exactly one twin in the second half, and the problem guarantees the list always has an even number of nodes, so you never need to handle an odd-length edge case.

The problem is rated Medium and appears frequently in coding interviews as a test of linked list manipulation skills. A brute-force approach converts the list to an array and accesses mirror indices directly in O(n) time but O(n) space. The interviewer-preferred approach uses O(1) space by reversing the second half in-place and walking both halves together.

The optimal solution reuses the exact same structural pattern as Palindrome Linked List (LeetCode 234): find the middle with slow/fast pointers, reverse the second half iteratively, then process pairs from both halves simultaneously. In Palindrome Linked List the "process" step compares values for equality. Here it computes the sum and tracks the maximum — same skeleton, different payload.

This three-step template applies to any problem that needs to pair nodes from opposite ends of a linked list. Once you internalize find-middle-and-reverse as a reusable module, problems like Reorder List (LeetCode 143) and this twin sum problem become straightforward applications of that module with different final-step logic.

The three steps are cleanly separable: each step has a single responsibility and a well-defined entry/exit state. Step 1 locates the second half start. Step 2 reverses from there. Step 3 exploits the reversed alignment to traverse twin pairs with a single loop. Keeping them mentally separate makes both implementation and debugging easier.

Use the classic slow/fast pointer technique. Initialize both slow and fast at head. Advance slow one step per iteration and fast two steps per iteration. When fast reaches null (or fast.next reaches null for even-length lists), slow is sitting at the start of the second half — exactly where you want to begin the reversal.

For an even-length list of n nodes, after the loop slow will be at index n/2. This is correct: the twin pairs are (0, n-1), (1, n-2), ..., (n/2-1, n/2), so the second half starts at index n/2. You do not need to find the last node of the first half or split the list; simply note slow's position as the reversal start.

After finding slow, you can optionally sever the connection between the two halves by tracking the node just before slow. In practice for this problem it is not necessary — you only need slow as the start of the reversal and head as the start of the first half.

Starting from slow, apply the standard iterative linked list reversal. Initialize prev = null and curr = slow. In each iteration, save curr.next, point curr.next to prev, advance prev to curr, then advance curr to the saved next. When curr becomes null, prev is the new head of the reversed second half.

After reversal, the reversed second half's head (prev) points to what was the last node of the original list. Traversing this reversed half gives you the twin partners in order: the first node of the reversed half pairs with head, the second node pairs with head.next, and so on through the center.

The reversal is destructive — it modifies the second half's next pointers in-place. This is acceptable here because you only need a single forward pass through the pairs after reversal. If the problem required restoring the list, you would reverse again after processing, as done in Palindrome Linked List's full implementation.

With the first half starting at head and the reversed second half starting at prev, initialize a maxSum variable to 0. In each iteration compute the current twin sum as first.val + second.val, update maxSum if this sum is larger, then advance both first = first.next and second = second.next. The loop runs for exactly n/2 iterations, covering all twin pairs.

The termination condition is when second (the reversed second half pointer) reaches null. Because the second half has exactly n/2 nodes, this naturally processes all pairs without needing a separate counter. Both pointers advance in lockstep, so first also exhausts its half simultaneously.

After the loop, maxSum holds the answer. The overall algorithm is O(n) time — one pass for slow/fast, one pass for reversal, one pass for twin sum — and O(1) space since only a constant number of pointers are used at any time. No auxiliary array, no stack, no recursion.

Python three-phase implementation: def pairSum(head): slow, fast = head, head; while fast and fast.next: slow = slow.next; fast = fast.next.next; prev, curr = None, slow; while curr: curr.next, prev, curr = prev, curr, curr.next; first, second, res = head, prev, 0; while second: res = max(res, first.val + second.val); first = first.next; second = second.next; return res. Each phase is a compact while loop; the walrus-operator-style tuple assignment in the reversal keeps it concise.

Java implementation: public int pairSum(ListNode head) { ListNode slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } ListNode prev = null, curr = slow; while (curr != null) { ListNode next = curr.next; curr.next = prev; prev = curr; curr = next; } int max = 0; ListNode first = head, second = prev; while (second != null) { max = Math.max(max, first.val + second.val); first = first.next; second = second.next; } return max; }. Time O(n), space O(1).

Stack-based alternative for simpler code at O(n) space: push the first half onto a stack while traversing to find the midpoint, then pop from the stack while traversing the second half. Each pop gives you the twin partner. This is cleaner to write but uses O(n/2) extra space. In interviews, always mention both approaches and explain why the reversal approach is preferred for optimal space complexity.

Palindrome Linked List (LeetCode 234) is the closest relative and the direct template for this problem. It uses identical slow/fast + reverse mechanics; the only difference is that the final pass compares values rather than summing them. Mastering Palindrome Linked List gives you Maximum Twin Sum almost for free.

Reorder List (LeetCode 143) uses the same find-middle and reverse-second-half steps but then interleaves the two halves instead of processing pairs. Middle of the Linked List (LeetCode 876) is the isolated first step — just finding the midpoint — and is worth practicing separately to build confidence with slow/fast pointer termination conditions.

Together, Palindrome Linked List, Maximum Twin Sum, Reorder List, and Middle of Linked List form the linked list half-and-mirror family. All four share the find-middle-then-process structure. Once you can write the slow/fast pointer and iterative reversal from memory, you can solve any problem in this family by plugging in the appropriate final-step logic.