※ 引述《Neuenmuller (蘇菲・諾伊恩謬拉)》之銘言：
: Leetcode 75 裡面其中一題
: https://leetcode.com/problems/maximum-twin-sum-of-a-linked-list/
: 剛開始我猜大概很簡單的把東西全塞進vector大概也能過
: 但是八成是要你用fast / slow pointer去找中間
: 最好是能one pass解
我的思路是先跑一次迴圈找數量
然後用遞迴往裡面跑
跑到中間的時候折返回來
然後就把節點跟折返節點的值加起來
例如
0-> 1-> 2-> 3-> 4-> 5↓
11<-10<- 9<- 8<- 7<- 6
雖然這樣空間複雜度是一
但是實際上堆疊用了不少的記憶體
最後時間打敗54% 空間打敗47%
完全沒有比較好
TS code:
function pairSum (head: ListNode | null): number {
let maxSum = 0
let n = 0
let node = head
while (node != null) {
n++;
node = node.next
}
const findSum = (node: ListNode, index: number): ListNode => {
if (index === n / 2 - 1) {
const returnNode = node.next
maxSum = Math.max(maxSum, node.val + returnNode.val)
return returnNode.next
}
if (index < n / 2) {
const returnNode = findSum(node.next, index + 1)
maxSum = Math.max(maxSum, node.val + returnNode.val)
return returnNode.next
}
return node.next
}
findSum(head, 0)
return maxSum
}

吃堆疊的話空間複雜度能算是1嗎？