2130. Maximum Twin Sum of a Linked List

題目 / Problem

中文：給定一個長度為偶數 n 的鏈結串列（linked list）的頭節點 head。第 i 個節點（從 0 開始編號）的「孿生節點」（twin）是第 (n-1-i) 個節點，其中 0 <= i <= n/2 - 1。也就是第一個節點配最後一個、第二個配倒數第二個，依此類推。一對孿生節點的值相加稱為「孿生和」（twin sum）。請回傳所有孿生和當中的最大值。

English: You are given the head of a linked list with even length n. Node i (0-indexed) and node n-1-i are "twins" — the first node pairs with the last, the second with the second-to-last, and so on. The "twin sum" is the sum of a node and its twin. Return the maximum twin sum across all pairs.

Constraints / 限制 - 節點數量是偶數，範圍 [2, 10^5] / The number of nodes is even, in range [2, 10^5]. - 1 <= Node.val <= 10^5.

Worked Example / 範例

Input:  head = [5,4,2,1]
Output: 6

配對：node0+node3 = 5+1 = 6，node1+node2 = 4+2 = 6。最大值是 6。 Pairs: 5+1=6 and 4+2=6, so the maximum twin sum is 6.

名詞解釋 / Glossary

• 鏈結串列 / linked list：一種資料結構，由一連串「節點」組成，每個節點存一個值 val 和一個指向下一個節點的指標 next。你只能從頭開始一個一個往後走，不能像陣列那樣用索引直接跳到中間。
• 節點 / node：鏈結串列的基本單位，包含資料 val 和指標 next（next 指向下一個節點，最後一個節點的 next 是 NULL）。
• 指標 / pointer：一個變數，存的是另一個物件（這裡是節點）的「記憶體位址」。p->val 表示「順著指標 p 找到那個節點，取它的 val」。
• 雙指針 / two pointers：用兩個指標同時掃描資料的技巧。本題讓一個指標從前半起點走、另一個從後半起點走，同時前進來湊出每一對孿生和。
• 反轉鏈結串列 / reversing a linked list：把箭頭方向掉頭，讓原本 A->B->C 變成 C->B->A。常用「三指標」逐步把每個節點的 next 改成指向前一個節點。
• 快慢指針 / slow-fast pointers：找中點的技巧。慢指標一次走一步、快指標一次走兩步；當快指標到尾端時，慢指標剛好在中間。
• 原地修改 / in-place：不另外開一個大陣列，直接在原本的結構上動手腳，藉此把額外空間降到 O(1)。
• 時間/空間複雜度 / time & space complexity：用 O(...) 描述「資料量變大時，花的時間/記憶體大致怎麼成長」。n 在這裡指節點數量。

思路

最直覺的暴力法（brute force）是：先把整條鏈結串列走一遍，把每個節點的值依序存進一個陣列。因為鏈結串列不能像陣列那樣用索引直接跳到第 n-1-i 個節點，所以先「攤平」成陣列後，孿生和就很好算：用兩個索引 left = 0 和 right = n-1，把 arr[left] + arr[right] 算出來、更新最大值，然後 left++、right--，直到兩者相遇。這個做法完全正確，時間是 O(n)，但需要一個額外的陣列，空間是 O(n)。對於 n 高達 10^5 的情況雖然能過，但我們可以做得更省。

更省空間的關鍵觀察是：孿生節點其實就是「前半段的第 i 個」和「後半段倒過來的第 i 個」。所以我們不需要整個陣列，只要能讓「後半段」也能從前往後走就好——這就是反轉的用處。具體三步：第一步用快慢指針找到中點（慢指標每次一步、快指標每次兩步，快指標到尾端時慢指標剛好在中間）；第二步把後半段就地反轉，讓它的箭頭掉頭；第三步用兩個指標，一個從原本的頭、一個從反轉後的後半段頭，同時往後走，每一步 first->val + second->val 就是一對孿生和，取最大值即可。為什麼這樣對？因為反轉後，後半段的第一個節點正好是原本的最後一個節點，也就是頭節點的孿生；兩指標同步前進，每一步都精確對上一對孿生。這個做法時間 O(n)、空間 O(1)。

The brute-force idea is simple: walk the whole list once and copy every value into an array. We do this because a linked list can't jump directly to index n-1-i the way an array can — you can only step forward node by node. Once flattened into an array, twin sums are easy: set left = 0, right = n-1, compute arr[left] + arr[right], track the max, then move left++ and right-- until they meet. This is correct and runs in O(n) time, but it uses an O(n) array.

To save space, notice that a twin is just "the i-th node from the front" paired with "the i-th node of the reversed back half." So instead of storing everything, we make the back half traversable front-to-front by reversing it. Three steps: (1) find the middle with slow/fast pointers — slow moves one node at a time, fast two, so when fast reaches the end slow sits at the midpoint; (2) reverse the second half in place by flipping each node's next to point backward; (3) walk one pointer from the original head and another from the reversed second half simultaneously — at each step first->val + second->val is exactly one twin sum, and we keep the maximum. It works because after reversal the first node of the back half is the original last node, i.e. the head's twin, and stepping both pointers in lockstep lines up every twin pair. This runs in O(n) time and O(1) extra space.

逐步走查 / Walkthrough

以 head = [5,4,2,1]（n = 4）為例 / Using head = [5,4,2,1] (n = 4):

Step 1 — 找中點 / Find middle (slow/fast):

fast 變成 NULL，迴圈停止，slow 指向 2，這就是後半段的起點。/ fast is NULL, loop stops; slow points at 2, the start of the back half.

Step 2 — 反轉後半段 / Reverse the second half ([2,1] → [1,2]):

反轉後後半段是 1 -> 2。前半段仍是 5 -> 4。/ Back half is now 1 -> 2; front half is still 5 -> 4.

Step 3 — 雙指針求孿生和 / Two pointers for twin sums:

回傳 6。/ Return 6. ✅

Solution — C

// 演算法 / 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
}

Solution — C++

// 演算法 / 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
    }
};

複雜度 / Complexity

• Time: O(n) — 找中點走半條串列、反轉走半條、雙指針走半條，每一步都是常數時間，總共是 n 的常數倍，所以是 O(n)。n 是節點數量。/ Finding the middle, reversing, and the two-pointer pass each touch at most half the list with constant work per node, summing to a constant multiple of n. n is the number of nodes.
• Space: O(1) — 只用了幾個指標變數（slow、fast、prev、cur、first、second）和一個整數，與 n 無關，沒有額外配置陣列。反轉是原地進行的。/ Only a handful of pointer variables and one integer are used, independent of n. The reversal is done in place — no extra array.

Pitfalls & Edge Cases

• 快指針的迴圈條件 / Fast-pointer loop condition：必須同時檢查 fast != NULL && fast->next != NULL。因為 fast 一次走兩步，若漏檢查就可能對 NULL 做 ->next，造成程式崩潰。/ You must check both fast and fast->next before stepping two nodes, otherwise you dereference NULL and crash.
• 反轉前先存 next / Save next before reversing：cur->next = prev 會覆蓋掉原本的 next，所以一定要先用 nxt 暫存，否則就找不到後面的節點，串列直接斷掉。/ cur->next = prev overwrites the original link, so you must stash nxt first or you lose the rest of the list.
• 迴圈停止條件用 second / Loop on second, not first：反轉後後半段的長度恰好是前半段的一半對應，用 second != NULL 結束最安全；因為長度保證偶數，兩半剛好等長，配對不會漏也不會多。/ Stop when second becomes NULL; since n is even the halves are equal length, so every twin is paired exactly once.
• 整數溢位免擔心 / No overflow worry：每個值最多 10^5，兩個相加最多 2×10^5，遠在 32 位元 int 範圍內，不需要 long long。/ Two values sum to at most 200000, well within int range — no need for a wider type.
• best 初值設 0 安全 / Initializing best = 0 is safe：因為 Node.val >= 1，任何孿生和至少是 2，一定會比初值 0 大，所以第一次比較必定更新。/ Since values are ≥ 1, every twin sum is ≥ 2 and beats the initial 0, so the max is always set correctly.
• 不要忘記回傳值的意義 / Return the max, not the last sum：題目要的是所有孿生和的最大值，不是某一對的和，所以要在迴圈裡持續比較更新。/ The answer is the maximum over all pairs, so you must compare every twin sum, not just return the last one.