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

/**
 * Definition for singly-linked list. / 單向鏈結串列的定義（LeetCode 已提供）
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
int pairSum(struct ListNode* head) {
    // slow 和 fast 都從頭出發 / both pointers start at head
    struct ListNode* slow = head;   // 慢指標，最後會停在中點 / ends at the middle
    struct ListNode* fast = head;   // 快指標，速度是慢指標兩倍 / moves twice as fast

    // 快指標每次走兩步，所以要確認 fast 和 fast->next 都存在才能再走
    // fast moves 2 steps, so both fast and fast->next must exist to continue
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;          // 慢指標前進一步 / slow advances 1 node
        fast = fast->next->next;    // 快指標前進兩步 / fast advances 2 nodes
    }
    // 迴圈結束時 slow 正好指向後半段的第一個節點
    // when the loop ends, slow points at the first node of the back half

    // --- 原地反轉後半段 / reverse the back half in place ---
    struct ListNode* prev = NULL;   // 反轉後新串列的「前一個」節點，起始為空 / previous node
    struct ListNode* cur = slow;    // 從後半段開頭開始反轉 / start reversing from the middle
    while (cur != NULL) {
        struct ListNode* nxt = cur->next; // 先記住下一個，否則改了指標就找不到 / save next first
        cur->next = prev;           // 把箭頭掉頭，指向前一個 / flip the arrow backward
        prev = cur;                 // prev 往前挪到目前節點 / move prev up
        cur = nxt;                  // cur 往前挪到剛存的下一個 / move cur up
    }
    // 反轉完成後 prev 是後半段反轉後的新頭 / prev is now the head of the reversed back half

    // --- 雙指針求最大孿生和 / two pointers for max twin sum ---
    struct ListNode* first = head;  // 從原始頭走前半段 / front pointer
    struct ListNode* second = prev; // 從反轉後的後半段頭走 / back pointer
    int best = 0;                   // 記錄目前最大孿生和 / running maximum
    while (second != NULL) {        // 後半段走完代表所有孿生都配完了 / back half exhausted = done
        int sum = first->val + second->val; // 一對孿生和 / one twin sum
        if (sum > best) best = sum;  // 比目前最大還大就更新 / update the max
        first = first->next;        // 前指標前進 / advance front
        second = second->next;      // 後指標前進 / advance back
    }
    return best;                    // 回傳最大孿生和 / return the answer
}