659. Maximum Twin Sum of a Linked List
You receive head, the first node of a singly linked list whose length n is even. Node i (0-indexed) and node n - 1 - i are called twins: the first node is twinned with the last, the second with the second-to-last, and so on, so every node belongs to exactly one twin pair.
Each pair has a twin sum — the values of its two nodes added together.
Return the largest twin sum anywhere in the list, as a single integer.
Example 1:
Input: head = [5, 4, 2, 1]
Output: 6
Explanation: The twins are (5, 1) and (4, 2). Both pairs add to 6, so the maximum twin sum is 6.
Example 2:
Input: head = [4, 2, 2, 3]
Output: 7
Explanation: The twins are (4, 3) with sum 7 and (2, 2) with sum 4. The maximum is 7.
Constraints:
- The list length n is even, with 2 ≤ n ≤ 10⁵
- 1 ≤ Node.val ≤ 10⁵
Hints:
Copy the node values into an array. Twins are just indices i and n - 1 - i, so two pointers walking in from both ends find every pair sum in one scan — at the cost of O(n) extra memory.
To do it in O(1) space: advance a slow and a fast pointer until fast runs off the list — slow then sits on the first node of the second half. Reverse that second half in place, then walk the two halves in lockstep; the k-th nodes of each half are twins.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: head = [5, 4, 2, 1]
Expected output: 6