MediumRating 1656
2130. Maximum Twin Sum of a Linked List
linked-listtwo-pointersstack
解題說明
Maximum Twin Sum of a Linked List
題目描述：給定一個長度為偶數 n 的鏈結串列，第 i 個節點（0-indexed）與第 n-1-i 個節點互為「孿生節點」，孿生和為兩者值之和。回傳所有孿生和中的最大值。
解題思路：關鍵在於如何在 O(1) 空間內同時訪問互為孿生的節點。最優方法：用快慢指標找到串列中點，將後半段反轉，然後用兩個指標分別從頭和（反轉後的）後半段開頭同步走，計算每對孿生和並取最大值。替代方法：用堆疊儲存前半段，再遍歷後半段逐一與堆疊彈出值配對。
C++ 解法
複雜度分析
時間複雜度：O(n) — 找中點 O(n/2)、反轉後半段 O(n/2)、雙指標掃描 O(n/2)，合計 O(n)。
空間複雜度：O(1) — 原地反轉後半段，只使用常數個指標。若改用堆疊方法則為 O(n/2) = O(n)。
虛擬碼
1. Find middle node using slow/fast pointers 2. Reverse the second half of the list starting from slow 3. Set left = head, right = head of reversed second half 4. While right != null: a. ans = max(ans, left.val + right.val) b. left = left.next, right = right.next 5. Return ans
其他解法
堆疊法 O(n) 空間：遍歷串列同時用快慢指標判斷前半段；將前半段節點值壓入堆疊，然後繼續遍歷後半段，每個節點值與堆疊彈出值相加，取最大值。實作更直觀，但需 O(n/2) 額外空間。
陣列法 O(n) 空間：先將所有節點值存入陣列，再用雙指標從兩端向中間計算孿生和。程式碼最簡潔，但同樣需 O(n) 空間。
延伸思考
- 若串列長度為奇數，「孿生」的定義無法完美對稱，此題為何保證長度必為偶數？若允許奇數長度，中間節點應如何處理？
- 原地反轉串列後半段會破壞原始結構。若要求保持串列不變，應如何修改演算法？
- 本題可以用兩次遍歷（第一次計算長度，第二次定位孿生對）解決嗎？與快慢指標方法相比有何優劣？