LC2130 Maximum Twin Sum of a Linked List 🟡

This is the boss fight of the section — compose three moves from earlier problems: Fast & Slow (p29) + Reverse (p31) + walk two chains.

1. Mindset Shift

The hard part: a linked list can’t walk backward — adding a front node to its twin at the back is awkward.

Key insight: find the middle with Fast & Slow → reverse the second half so it faces the same way as the first → walk from both ends and track the max twin sum.

The easy way is dump every value into a list and add vals[i] + vals[n-1-i] — correct but Space O(n). This approach stays in-place at Space O(1).

2. The Logic — 3 Steps

Split the work into three clear stages:

1. Find middle — Fast & Slow walk; when fast falls off, slow sits at the head of the second half (n is always even)
2. Reverse second half — reuse the p31 flip from slow; prev becomes the new head (the old last node moves to the front)
3. Pair and add — first at head · second at prev; walk together; first.val + second.val is one twin sum; keep the max

3. LeetCode-Ready Code

Three stages lined up in one function:

# 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:
        # Stage 1: find middle with Fast & Slow
        slow = head
        fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        # slow is now the head of the second half

        # Stage 2: reverse the second half (p31 move)
        prev = None
        cur = slow
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        # prev is the head of the reversed second half

        # Stage 3: walk both halves, track max twin sum
        best = 0
        first = head
        second = prev
        while second:               # halves are the same length
            best = max(best, first.val + second.val)
            first = first.next
            second = second.next
        return best

4. Dry Run — 5 → 4 → 2 → 1

The | mark splits pieces: left = first half · right = second half (being reversed / paired) — final answer 6

5. Edge Cases & Pitfalls

The "crossed link at the midpoint" case:

• After reversing the second half, the link at the midpoint may look a bit crossed
• It doesn’t matter — we only walk n/2 steps and stop when second is None

6. Time & Space Complexity

• Time O(n) — find middle + reverse second half + pair walk are all linear
• Space O(1) — rewire in place; no copy into a new list