資訊專欄INFORMATION COLUMN
摘要：需求實(shí)現(xiàn)一個函數(shù)，把一個鏈表切分成兩個。子鏈表的節(jié)點(diǎn)應(yīng)該是在父鏈表中交替出現(xiàn)的。所以整個算法的解法就能很容易地用表示。唯一需要考慮的就是在每個循環(huán)體中判斷節(jié)點(diǎn)該插入哪個鏈表。也有人使用持續(xù)增長的配合取余來做，比如。
TL;DR
把一個鏈表交替切分成兩個，系列目錄見 前言和目錄 。
需求實(shí)現(xiàn)一個 alternatingSplit() 函數(shù)，把一個鏈表切分成兩個。子鏈表的節(jié)點(diǎn)應(yīng)該是在父鏈表中交替出現(xiàn)的。如果原鏈表是 a -> b -> a -> b -> a -> null ，則兩個子鏈表分別為 a -> a -> a -> null 和 b -> b -> null 。
var list = 1 -> 2 -> 3 -> 4 -> 5 -> null alternatingSplit(list).first === 1 -> 3 -> 5 -> null alternatingSplit(list).second === 2 -> 4 -> null
為了簡化結(jié)果，函數(shù)會返回一個 Context 對象來保存兩個子鏈表，Context 結(jié)構(gòu)如下所示：
function Context(first, second) {
this.first = first
this.second = second
}
如果原鏈表為 null 或者只有一個節(jié)點(diǎn)，應(yīng)該拋出異常。
遞歸版本代碼如下：
function alternatingSplit(head) {
if (!head || !head.next) throw new Error("invalid arguments")
return new Context(split(head), split(head.next))
}
function split(head) {
const list = new Node(head.data)
if (head.next && head.next.next) list.next = split(head.next.next)
return list
}
這個解法的核心思路在于 split ，這個方法接收一個鏈表并返回一個以奇數(shù)位的節(jié)點(diǎn)組成的子鏈表。所以整個算法的解法就能很容易地用 new Context(split(head), split(head.next)) 表示。
另一個遞歸版本代碼如下：
function alternatingSplitV2(head) {
if (!head || !head.next) throw new Error("invalid arguments")
return new Context(...splitV2(head))
}
function splitV2(head) {
if (!head) return [null, null]
const first = new Node(head.data)
const [second, firstNext] = splitV2(head.next)
first.next = firstNext
return [first, second]
}
這里的 splitV2 的作用跟整個算法的含義一樣 -- 接收一個鏈表并返回交叉分割的兩個子鏈表（以數(shù)組表示）。第一個子鏈表的頭自然是 new Node(head.data) ，第二個子鏈表呢？它其實(shí)是 splitV2(head.next) 的第一個子鏈表（見第 4 行）。理解這個邏輯后就能明白遞歸過程。
循環(huán)版本代碼如下：
function alternatingSplitV3(head) {
if (!head || !head.next) throw new Error("invalid arguments")
const first = new Node()
const second = new Node()
const tails = [first, second]
for (let node = head, idx = 0; node; node = node.next, idx = idx ? 0 : 1) {
tails[idx].next = new Node(node.data)
tails[idx] = tails[idx].next
}
return new Context(first.next, second.next)
}
這個思路是，先用兩個變量代表子鏈表，然后對整個鏈表進(jìn)行一次遍歷，分別把節(jié)點(diǎn)交替插入每個子鏈表中。唯一需要考慮的就是在每個循環(huán)體中判斷節(jié)點(diǎn)該插入哪個鏈表。我用的是 idx 變量，在每輪循環(huán)中把它交替設(shè)置成 0 和 1 。也有人使用持續(xù)增長的 idx 配合取余來做，比如 idx % 2 。做法有很多種，就不贅述了。
這里也用了 dummy node 的技巧來簡化 “判斷首節(jié)點(diǎn)是否為空” 的情況。關(guān)于這個技巧可以看看 Insert Nth Node
參考資料Codewars Kata
GitHub 的代碼實(shí)現(xiàn)
GitHub 的測試
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/81377.html
摘要：我打算寫一個鏈表操作的系列，來自的系列，實(shí)現(xiàn)語言是。通過自己實(shí)現(xiàn)一個鏈表和常用操作，可以加深理解這類數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)。鏈表經(jīng)常用來訓(xùn)練指針操作，雖然這只對適用，但等高級語言中控制引用的思路其實(shí)也差不多。 TL;DR 我打算寫一個鏈表操作的系列，來自 Codewars 的 Linked List 系列 kata ，實(shí)現(xiàn)語言是 JavaScript 。這篇是開篇，簡單描述了一下我寫這個的目...
摘要：需求實(shí)現(xiàn)函數(shù)把鏈表居中切分成兩個子鏈表一個前半部分，另一個后半部分。提示一個簡單的做法是計(jì)算鏈表的長度，然后除以得出前半部分的長度，最后分割鏈表。最后用把數(shù)組轉(zhuǎn)回鏈表。參考資料的代碼實(shí)現(xiàn)的測試 TL;DR 把一個鏈表居中切分成兩個，系列目錄見 前言和目錄 。 需求 實(shí)現(xiàn)函數(shù) frontBackSplit() 把鏈表居中切分成兩個子鏈表 -- 一個前半部分，另一個后半部分。如果節(jié)點(diǎn)數(shù)為奇...
摘要：需求實(shí)現(xiàn)函數(shù)進(jìn)行歸并排序。解法歸并排序的運(yùn)行方式是，遞歸的把一個大鏈表切分成兩個小鏈表。切分到最后就全是單節(jié)點(diǎn)鏈表了，而單節(jié)點(diǎn)鏈表可以被認(rèn)為是已經(jīng)排好序的。這時候再兩兩合并，最終會得到一個完整的已排序鏈表。用把排好序的兩個鏈表合并起來。 TL;DR 對鏈表進(jìn)行歸并排序，系列目錄見 前言和目錄 。 需求 實(shí)現(xiàn)函數(shù) mergeSort() 進(jìn)行歸并排序。注意這種排序法需要使用遞歸。在 fr...
摘要：需求實(shí)現(xiàn)函數(shù)把兩個鏈表合并成一個。新鏈表的節(jié)點(diǎn)是交叉從兩個鏈表中取的。通過行的調(diào)換指針，我們可以保證下一次循環(huán)就是對另一個鏈表進(jìn)行操作了。這樣一直遍歷到兩個鏈表末尾，返回結(jié)束。參考資料的代碼實(shí)現(xiàn)的測試 TL;DR 把兩個鏈表洗牌合并成一個，系列目錄見 前言和目錄 。 需求 實(shí)現(xiàn)函數(shù) shuffleMerge() 把兩個鏈表合并成一個。新鏈表的節(jié)點(diǎn)是交叉從兩個鏈表中取的。這叫洗牌合并。舉...
閱讀 2795·2023-04-26 01:47
閱讀 3601·2023-04-25 23:45
閱讀 2481·2021-10-13 09:39
閱讀 617·2021-10-09 09:44
閱讀 1807·2021-09-22 15:59
閱讀 2786·2021-09-13 10:33
閱讀 1733·2021-09-03 10:30
閱讀 667·2019-08-30 15:53
