給定一個單向鏈表，其中每個元素都包含一個數字和一個指向串列頭部的指標。將第一個和最后一個資料相加并洗掉這些節點。然后將結果鏈表的第一個和最后一個資料相加并洗掉這兩個節點。
繼續這樣做，直到串列變空。我們必須在 O(1) 空間復雜度中找到從結果總和中獲得的最大總和。
該串列是具有偶數節點的單向鏈表。
我的想法：
- 一種方法是在每次迭代時將指標移動到最后一個元素，洗掉節點，并保留一個 maxSum 變數。這可能不是一個有效的解決方案。
uj5u.com熱心網友回復：
如果我理解正確的話，這個鏈表中的一個節點有兩個指標：一個指向下一個節點的指標和一個指向串列中第一個節點的指標。
有幾種方法可以解決這個問題。這是一個：
- 遍歷串列并更改每個節點中的頭指標以參考前一個節點：這將為您提供一個雙向鏈表。保留指向最后一個節點的指標。
- 現在，您可以從串列的兩端開始串聯遍歷并朝著彼此走去。
- 在遍歷程序中洗掉節點并不是真正需要的。您甚至可以將串列恢復到第二步中的原始狀態。
甚至可以在每個節點中沒有這個額外的頭指標的情況下做到這一點。在這種情況下，反轉串列的后半部分。
這是第一個想法的實作，在 JavaScript 中：
class Node {
constructor(data, head) {
this.data = data;
this.head = head || this; // default is node itself
this.next = null;
}
}
function createList(...values) {
if (!values) return null;
let head = new Node(values.shift()); // First value
let tail = head;
for (let value of values) { // Remaining values
tail.next = new Node(value, head);
tail = tail.next;
}
return tail.head;
}
function maxPairSum(head) {
if (!head) return -Infinity;
// Make doubly linked list, (ab)using node's head member
let tail;
for (tail = head; tail.next; tail = tail.next) {
tail.next.head = tail; // Next gets reference to previous
}
// Tandem walk, towards center
let maxSum = -Infinity;
for (let curr = head; curr != tail && curr != tail.next; curr = curr.next) {
maxSum = Math.max(maxSum, curr.data tail.data);
tail = tail.head; // Is actually a reference to previous
}
// Restore head references (optional)
for (let curr = head; curr; curr = curr.next) {
curr.head = head;
}
return maxSum;
}
// Example run
let head = createList(2, 5, 1, 5, 4, 6);
let maxSum = maxPairSum(head);
console.log(maxSum); // 9...如果您真的想洗掉串列，只需清除head參考即可。在 JavaScript 中，垃圾收集器會釋放無法訪問的記憶體；在其他一些語言（如 C）中，在清除對頭節點的參考之前，您需要明確釋放每個節點占用的記憶體。
uj5u.com熱心網友回復：
將所有鏈表值元素推送到堆疊如何，1->2->3->4例如，堆疊將是1234. 之后，我們一一求和并洗掉每個鏈表，存盤我們得到的最大值。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/367791.html
上一篇：收集添加和洗掉元素時的代碼改進