※ 引述《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 } -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1698896158.A.785.html