Maximum Twin Sum of a Linked List
題目描述
給定一個偶數長度的 Linked List，節點 i 和節點 n-1-i 互為 twin。回傳最大的 twin sum（twin 兩節點值之和）。
輸入: [5,4,2,1]
輸出: 6
解釋: twin pairs: (5,1), (4,2)，最大和 = 5+1 = 6
輸入: [4,2,2,3]
輸出: 7
解釋: twin pairs: (4,3), (2,2)，最大和 = 4+3 = 7
解題思路
找中點
slow 每走 1 步、fast 走 2 步，fast 到尾時 slow 在中點（後半段起點）
反轉後半段
從 slow 開始用 prev/curr 迭代反轉，讓後半段尾變頭
配對比較
left 從 head 往右走、right 從反轉後的頭往右走，每步計算 left.val + right.val
取最大值
用 maxSum = max(maxSum, left.val + right.val) 持續更新最大 twin sum
程式碼
C#
public class Solution {
public int PairSum(ListNode head) {
// 1. 快慢指針找中點
var slow = head;
var fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 2. 反轉後半段
ListNode prev = null;
while (slow != null) {
var next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
// 3. 配對比較，求最大 twin sum
int maxSum = 0;
var left = head;
var right = prev;
while (right != null) {
maxSum = Math.Max(maxSum, left.val + right.val);
left = left.next;
right = right.next;
}
return maxSum;
}
}TypeScript
function pairSum(head: ListNode | null): number {
// 1. 快慢指針找中點
let slow = head;
let fast = head;
while (fast && fast.next) {
slow = slow!.next;
fast = fast.next.next;
}
// 2. 反轉後半段
let prev: ListNode | null = null;
while (slow) {
const next = slow.next;
slow.next = prev;
prev = slow;
slow = next;
}
// 3. 配對比較，求最大 twin sum
let maxSum = 0;
let left = head;
let right = prev;
while (right) {
maxSum = Math.max(maxSum, left!.val + right.val);
left = left!.next;
right = right.next;
}
return maxSum;
}Python
def pairSum(head: Optional[ListNode]) -> int:
# 1. 快慢指針找中點
slow, fast = head, head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
# 2. 反轉後半段
prev = None
while slow:
slow.next, prev, slow = prev, slow, slow.next
# 3. 配對比較，求最大 twin sum
max_sum = 0
left, right = head, prev
while right:
max_sum = max(max_sum, left.val + right.val)
left = left.next
right = right.next
return max_sum複雜度分析
| | Time | Space | |--|------|-------| | 本解法 | O(n) | O(1) |
Time 為 O(n) 是因為三個步驟各自遍歷半條鏈表：找中點 n/2 步、反轉 n/2 步、配對比較 n/2 步，合計 3n/2 = O(n)。Space 為 O(1) 是因為反轉在原鏈表上操作，只用了常數個指針。
邊界情況
- 最短鏈表（2 個節點）：
[1,2]只有一對 twin，直接回傳 1+2=3 - 所有值相同：如
[5,5,5,5]，每對 twin sum 都是 10，答案為 10 - 最大值在中間配對：如
[1,100,100,1]，需要正確配對 (1,1) 和 (100,100)，答案 200
圖解
圖表展示了 [5,4,2,1] 的處理流程：先找到中點 2、反轉後半段得到 1→2，然後 left=5 配 right=1（和 6）、left=4 配 right=2（和 6），最大 twin sum 為 6。
進階觀點
💡面試追問
Q: 除了反轉後半段，還有什麼方法？ A: 用 Stack 存前半段的值，再遍歷後半段時逐一 pop 配對。空間 O(n/2) = O(n)。也可以把所有值存入 Array 再用雙指針，同樣 O(n) 空間。反轉法是唯一 O(1) 空間的方案。
Q: 反轉後半段會破壞原鏈表，面試時要注意什麼？ A: 面試時先問面試官是否允許修改輸入。如果不允許，需要在計算完畢後再反轉一次恢復原狀，或改用 O(n) 空間的方案。
這題結合了三個基礎技巧：快慢指針、反轉 Linked List、雙指針遍歷。面試官常考這種「組合技」。
變體題：LC 234 Palindrome Linked List（同樣技巧，檢查是否回文）。
理解測驗
🤔 為什麼要反轉後半段而不是直接配對？
🤔 如果用 Stack 解這題，空間複雜度會是多少？