// 演算法 / Algorithm:
// 1) 快慢指針找中點 / slow-fast pointers find the middle.
// 2) 原地反轉後半段 / reverse the second half in place.
// 3) 兩指針同步前進，取孿生和最大值 / walk both halves, keep max twin sum.
// O(n) time, O(1) extra space.

/**
 * Definition for singly-linked list. / 單向鏈結串列定義
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int pairSum(ListNode* head) {
        // 快慢指針找中點 / find the middle with slow & fast pointers
        ListNode* slow = head;      // 走一步 / one step at a time
        ListNode* fast = head;      // 走兩步 / two steps at a time
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;      // 慢指標 +1 / slow advances by 1
            fast = fast->next->next;// 快指標 +2 / fast advances by 2
        }
        // slow 現在指向後半段第一個節點 / slow is now at the start of the back half

        // 原地反轉後半段 / reverse the back half in place
        ListNode* prev = nullptr;   // 反轉串列的前一節點 / previous node, starts empty
        ListNode* cur = slow;       // 從中點開始 / start from the middle
        while (cur != nullptr) {
            ListNode* nxt = cur->next; // 暫存下一個節點 / save next before we overwrite it
            cur->next = prev;       // 箭頭掉頭 / reverse the link
            prev = cur;             // prev 前進 / move prev forward
            cur = nxt;              // cur 前進 / move cur forward
        }
        // prev 是反轉後後半段的頭 / prev is the head of the reversed back half

        // 雙指針求最大孿生和 / two pointers compute the max twin sum
        ListNode* first = head;     // 前半段指標 / front pointer
        ListNode* second = prev;    // 後半段指標 / back pointer
        int best = 0;               // 目前最大值 / running maximum
        while (second != nullptr) { // 後半段走完即結束 / stop when back half ends
            // std::max 回傳兩者較大的，比手寫 if 更簡潔 / std::max returns the larger of two
            best = std::max(best, first->val + second->val); // 更新最大孿生和 / update max
            first = first->next;    // 前進 / advance front
            second = second->next;  // 前進 / advance back
        }
        return best;                // 回傳答案 / return the result
    }
};