Maximum Twin Sum of a Linked List

Align the twins

Twin nodes are equidistant from opposite ends. Find the midpoint using slow and fast pointers, reverse the second half in place, then advance one pointer from the head and one through the reversed half. Each step now exposes a twin pair, so update the maximum of their values' sum. For an even-length list, ensure the chosen midpoint starts the second half rather than skipping its first node.

Explain tradeoffs

An array solution is straightforward but uses O(n) extra space. Reversing half the list uses O(1) auxiliary space and keeps time O(n). Mention whether the caller permits mutation; if not, reverse the second half again after computing the answer. Check the minimum valid list length, duplicate values, and very large sums. Avoid trying to compare head and tail without random access, which would repeatedly rescan the list and become quadratic.