Maximum Twin Sum of a Linked List
Maximum Twin Sum of a Linked List: in a list of even length n, node i is the twin of node n-1-i. Return the maximum sum of any twin pair.
- The number of nodes is an even integer in the range [2, 10⁵].
- 1 <= Node.val <= 10⁵
Intuition
Twins sit symmetrically about the centre, but a singly linked list cannot be read backwards. Split it in half, reverse the second half in place, and then walk both halves forward together — each step pairs a node with its twin, and no extra memory is needed.
Split, reverse, then walk in parallel is the standard manoeuvre whenever a singly linked list must be compared front-to-back. The same three steps solve Palindrome Linked List and Reorder List — recognising it turns an apparently backwards-facing problem into two forward walks.
Approach
Before reading on: the twin of the first node is the last, which you cannot reach going backwards. What single structural change would let you walk toward both ends at once? Aim for O(n) time and O(1) space.
Locate the centre with fast and slow pointers
Advance slow by one and fast by two. When fast reaches the end, slow marks the start of the second half. Because the length is guaranteed even, the split is exact — slow lands precisely on node n/2 with no leftover middle element to handle. This costs one pass and no extra storage.
Reverse the second half in place
Walk the second half rewriting each next pointer to point backwards, keeping prev, curr, and next as the standard three-pointer reversal. Afterwards the former tail is the head of the reversed portion. Now the first node of half one and the first node of reversed half two are twins — index 0 with index n-1 — and every subsequent step keeps that pairing.
Walk both halves and take the maximum
Advance one pointer through the first half and one through the reversed second half, summing the pair at each step and keeping the largest. The loop runs n/2 times and ends when the reversed half is exhausted. Total cost is O(n) time and O(1) space. The alternative — pushing every value into an array and pairing by index — is simpler to write but uses O(n) memory, which the O(1) follow-up rules out.
Solution & live demo
Common pitfalls
Collecting values into a list
vals = []
while head:
vals.append(head.val)
head = head.next# split, reverse in place, walk both halves
Correct and easy, but it uses O(n) memory. The point of the problem is the O(1)-space follow-up, which requires the in-place reversal.
Reversing the whole list instead of half
prev = None curr = head while curr: ... # from the head
# reverse starting at slow, the midpoint
Reversing everything destroys the first half you still need to walk forward, so the twin pairing is lost. Only the portion from the midpoint onwards should be flipped.
Looping while the first half is non-null
while first:
while second:
After the split the first half may still link into the reversed portion, so iterating on first can run past n/2 pairs and double-count. The reversed half terminates exactly at the midpoint, making it the correct loop guard.
Edge cases
One twin pair; the answer is their sum.
Every twin sum is identical, so the maximum is that value doubled.
Found on the first iteration; the loop still checks the rest.
The walk covers all n/2 pairs, so a late maximum is not missed.
Guaranteed by the constraints, so no odd-length middle node needs special handling.