Largest Sum of Symmetric List Partners

### Problem A singly linked list has even length `n`. Pair each node at zero-based position `i` in the first half with the node at position `n - 1 - i`. Return the greatest sum of the values in any such pair, using the supplied `ListNode* head` interface. ```cpp class Solution { public: int pairSum(ListNode* head); }; ``` ### Examples **Example 1:** ```text List values: [2,7,3,4] Output: 10 Explanation: The partner sums are 2+4=6 and 7+3=10. ``` **Example 2:** ```text List values: [8,5] Output: 13 Explanation: The two nodes form the only pair. ``` ### Constraints - The list length is even and lies in `[2,10^5]`. - Node values lie in `[1,10^5]`. ### Clarifying Questions This returns a numerical statistic; the list need not be modified. Partners are symmetric positions, not adjacent nodes. ```hint Inspect the structure What extra storage lets a forward-only list traversal access its values in reverse positional order? ``` ### Reasoning checkpoints - Use symmetric positions from opposite ends rather than adjacent nodes. - Compare every pair and return the largest value sum. - Retain the specified linked-list input protocol and handle the shortest valid two-node list. ### Optional extensions Can you use constant additional space while leaving the list unchanged when the call returns?