分裂鏈表到2個甚至包含的最小和最大數字

鑑於隨機整數鏈表列表，將它分成兩個新的鏈表，使得每個列表的元素之和的差值最大和列表的長度相差不超過1（在原始列表具有奇數個元素的情況下）。 我不能認爲列表中的數字是唯一的。分裂鏈表到2個甚至包含的最小和最大數字

我想到的算法是做原來的鏈表合併排序（爲O（n＆middot; log n）的時間，爲O（n）空間），然後使用遞歸函數走路列表的末尾來確定它的長度，在遞歸函數展開時進行分割。遞歸函數是O（n）的時間和爲O（n）空間。

這是最佳的解決方案？如果有人認爲它是相關的，我可以發佈我的代碼。

2011-02-09 Robert S. Barnes

- 得到兩個列表迭代上開始時，預先在各步驟前2層的元件，第二1個元件的每個步驟時首先到達列表末尾：在O（n）的時間和O（1）空間被分割如果你的鏈表實現保持一個大小的屬性，那麼你只需要在列表的中間走一半就可以把它切成兩半。（可能希望查看http://codereview.stackexchange.com！） – Jeremy 2011-02-09 12:48:22

@Jeremy Heiler：沒有大小的屬性，只是一個非常簡單的簡單鏈表，實際上只不過是一堆鏈接在一起的節點。 – 2011-02-09 12:52:09

除非您的考試要求您執行排序，否則您還可以使用Collections.sort進行排序。 – karakuricoder 2011-02-09 12:52:14

不，它不是最佳;你可以找到median of a list in O(n)，然後把它們中的一半放在一個列表中（小於中值或相等，直到列表大小爲n/2），另一半放在另一個列表中（（n + 1）/ 2）。它們的和差最大化，並且也沒有必要進行排序（爲O（n＆middot;的log（n））所有的事情都會在爲O（n）（時間和空間）

來源

2011-02-09 13:23:21

爲什麼要做你需要遞歸函數嗎？在排序列表時，你可以計算它的元素，然後把它分成兩半，這會降低O（n）的空間要求

即使在排序時你不能計算列表長度，它仍然可以。切割在第二

來源

2011-02-09 13:24:32 blaze

分裂鏈表到2個甚至包含的最小和最大數字

回答

相關問題