Description
在一個長度為偶數
n的鏈結串列中，第i個節點的 twin 是第n-1-i個節點。twin sum 是一對 twin 節點值的和。回傳最大的 twin sum。
Example:
Input: head = [5,4,2,1] Output: 6（5+1=6, 4+2=6）
Intuition#
核心思路：找到中點後反轉前半段（或後半段），然後同步遍歷計算 twin sum 的最大值。
- Twin 的配對方式是首尾對稱（第 0 個配第 n-1 個）
- 可以用 Stack 儲存前半段，遍歷後半段時逐一配對
- 最佳做法：快慢指針找中點 + 反轉前半段，O(1) 空間
Approaches#
1: Stack#
- 概念: 用快慢指針找到中點，將前半段壓入 Stack，再遍歷後半段同時彈出 Stack 計算配對和
- 時間複雜度:
O(n) - 空間複雜度:
O(n/2)=O(n)
class Solution {
fun pairSum(head: ListNode?): Int {
val stack = ArrayDeque<Int>()
var slow = head
var fast = head
while (fast?.next != null) {
stack.addLast(slow!!.`val`)
slow = slow.next
fast = fast.next?.next
}
var maxSum = 0
var curr = slow
while (curr != null) {
maxSum = maxOf(maxSum, curr.`val` + stack.removeLast())
curr = curr.next
}
return maxSum
}
}⭐2: Reverse First Half#
- 概念: 快慢指針找中點的同時反轉前半段，然後從中點和反轉後的前半段頭同步遍歷
- 時間複雜度:
O(n) - 空間複雜度:
O(1)
class Solution {
fun pairSum(head: ListNode?): Int {
var slow = head
var fast = head
var prev: ListNode? = null
// 快慢指針找中點，同時反轉前半段
while (fast?.next != null) {
fast = fast.next?.next
val next = slow?.next
slow?.next = prev
prev = slow
slow = next
}
// prev 是反轉後的前半段頭，slow 是後半段頭
var maxSum = 0
var left = prev
var right = slow
while (left != null && right != null) {
maxSum = maxOf(maxSum, left.`val` + right.`val`)
left = left.next
right = right.next
}
return maxSum
}
}🔑 Takeaways#
- Pattern: 鏈結串列的對稱配對問題，核心是找中點 + 反轉其中一半
- 關鍵技巧: 可以在快慢指針移動的同時反轉前半段，一次遍歷完成兩件事