※ 引述《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吗？