摘要:需求實(shí)現(xiàn)一個(gè)函數(shù),把源鏈表的頭結(jié)點(diǎn)移到目標(biāo)鏈表的開頭。要求是不能修改兩個(gè)鏈表的引用。跟前一個(gè)不同的是,這個(gè)是在不改變引用的情況下修改兩個(gè)鏈表自身。最優(yōu)的方案這個(gè)算法考的是對(duì)鏈表節(jié)點(diǎn)的插入和刪除。大致思路為對(duì)做刪除一個(gè)節(jié)點(diǎn)的操作。
TL;DR
用 in-place 的方式把一個(gè)鏈表的首節(jié)點(diǎn)移到另一個(gè)鏈表(不改變鏈表的引用),系列目錄見(jiàn) 前言和目錄 。
需求實(shí)現(xiàn)一個(gè) moveNode() 函數(shù),把源鏈表的頭結(jié)點(diǎn)移到目標(biāo)鏈表的開頭。要求是不能修改兩個(gè)鏈表的引用。
</>復(fù)制代碼
var source = 1 -> 2 -> 3 -> null
var dest = 4 -> 5 -> 6 -> null
moveNode(source, dest)
source === 2 -> 3 -> null
dest === 1 -> 4 -> 5 -> 6 -> null
當(dāng)碰到以下的情況應(yīng)該拋出異常:
源鏈表為 null
目標(biāo)鏈表為 null
源鏈表是空節(jié)點(diǎn),data 屬性為 null 的節(jié)點(diǎn)定義為空節(jié)點(diǎn)。
跟 前一個(gè) kata 不同的是,這個(gè) kata 是在不改變引用的情況下修改兩個(gè)鏈表自身。因此 moveNode() 函數(shù)不需要返回值。同時(shí)這個(gè) kata 也提出了 空節(jié)點(diǎn) 的概念。空節(jié)點(diǎn)會(huì)用于目標(biāo)鏈表為空的情況(為了保持引用),在函數(shù)執(zhí)行之后,目標(biāo)鏈表會(huì)由空節(jié)點(diǎn)變成一個(gè)包含一個(gè)節(jié)點(diǎn)的鏈表。
你可以使用 第一個(gè) kata 的 push 方法。
最優(yōu)的方案這個(gè)算法考的是對(duì)鏈表節(jié)點(diǎn)的插入和刪除。基本只對(duì) source 和 dest 分別做一次操作,所以不用區(qū)分遞歸和循環(huán)。大致思路為:
對(duì) source 做刪除一個(gè)節(jié)點(diǎn)的操作。如果只有一個(gè)節(jié)點(diǎn)就直接置空。如果有多個(gè)節(jié)點(diǎn),就把第二個(gè)節(jié)點(diǎn)的值賦給頭節(jié)點(diǎn),然后讓頭結(jié)點(diǎn)指向第三個(gè)節(jié)點(diǎn)。
對(duì) dest 做插入一個(gè)節(jié)點(diǎn)的操作。如果頭結(jié)點(diǎn)為空就直接賦值,否則把頭結(jié)點(diǎn)復(fù)制一份,作為第二個(gè)節(jié)點(diǎn)插入到鏈表中,再把新值賦給頭結(jié)點(diǎn)。
代碼如下:
</>復(fù)制代碼
function moveNode(source, dest) {
if (!source || !dest || source.data === null) throw new Error("invalid arguments")
const data = source.data
if (source.next) {
source.data = source.next.data
source.next = source.next.next
} else {
source.data = null
}
if (dest.data === null) {
dest.data = data
} else {
dest.next = new Node(dest.data, dest.next)
dest.data = data
}
}
遞歸方案
這是我最開始思考的方案,差別在于對(duì) dest 如何插入新節(jié)點(diǎn)的處理上用了遞歸。思路是把所有節(jié)點(diǎn)的 data 往后移一位,即把新值賦給第一個(gè)節(jié)點(diǎn),第一個(gè)節(jié)點(diǎn)的值賦給第二個(gè)節(jié)點(diǎn),第二個(gè)節(jié)點(diǎn)的值賦給第三個(gè)節(jié)點(diǎn),以此類推。但實(shí)際操作中的順序必須是反的,就是把倒數(shù)第二個(gè)節(jié)點(diǎn)的值賦給最后一個(gè)節(jié)點(diǎn),倒數(shù)第三個(gè)節(jié)點(diǎn)的值賦給倒數(shù)第二個(gè)節(jié)點(diǎn)…… 這個(gè)思路對(duì) dest 操作了 N 次,不如上一個(gè)解法的 1 次操作高效。不過(guò)也算是個(gè)有意思的遞歸用例,所以我仍然把它放了上來(lái)。
代碼如下,主要看 pushInPlaceV2 :
</>復(fù)制代碼
function moveNodeV2(source, dest) {
if (source === null || dest === null || source.isEmpty()) {
throw new Error("invalid arguments")
}
pushInPlaceV2(dest, source.data)
if (source.next) {
source.data = source.next.data
source.next = source.next.next
} else {
source.data = null
}
}
function pushInPlaceV2(head, data) {
if (!head) return new Node(data)
if (!head.isEmpty()) head.next = pushInPlaceV2(head.next, head.data)
head.data = data
return head
}
總結(jié)
總是使用遞歸會(huì)產(chǎn)生慣性,導(dǎo)致忽略了數(shù)據(jù)結(jié)構(gòu)的基本特性。鏈表的特性就是插入和刪除的便利,改改引用就成了。
算法相關(guān)的代碼和測(cè)試我都放在 GitHub 上,如果對(duì)你有幫助請(qǐng)幫我點(diǎn)個(gè)贊!
參考資料Codewars Kata
GitHub 的代碼實(shí)現(xiàn)
GitHub 的測(cè)試
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://m.specialneedsforspecialkids.com/yun/81149.html
摘要:我打算寫一個(gè)鏈表操作的系列,來(lái)自的系列,實(shí)現(xiàn)語(yǔ)言是。通過(guò)自己實(shí)現(xiàn)一個(gè)鏈表和常用操作,可以加深理解這類數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)。鏈表經(jīng)常用來(lái)訓(xùn)練指針操作,雖然這只對(duì)適用,但等高級(jí)語(yǔ)言中控制引用的思路其實(shí)也差不多。 TL;DR 我打算寫一個(gè)鏈表操作的系列,來(lái)自 Codewars 的 Linked List 系列 kata ,實(shí)現(xiàn)語(yǔ)言是 JavaScript 。這篇是開篇,簡(jiǎn)單描述了一下我寫這個(gè)的目...
摘要:需求實(shí)現(xiàn)一個(gè)函數(shù),把源鏈表的頭節(jié)點(diǎn)移到目標(biāo)鏈表。當(dāng)源鏈表為空時(shí)函數(shù)應(yīng)拋出異常。為了簡(jiǎn)化起見(jiàn),我們會(huì)用一個(gè)對(duì)象來(lái)存儲(chǔ)改變后的源鏈表和目標(biāo)鏈表的引用。它也是函數(shù)的返回值。解法配合,這個(gè)非常簡(jiǎn)單,注意這個(gè)函數(shù)沒(méi)有改變兩個(gè)鏈表本身。 TL;DR 把一個(gè)鏈表的首節(jié)點(diǎn)移到另一個(gè)鏈表。系列目錄見(jiàn) 前言和目錄 。 需求 實(shí)現(xiàn)一個(gè) moveNode() 函數(shù),把源鏈表的頭節(jié)點(diǎn)移到目標(biāo)鏈表。當(dāng)源鏈表為空時(shí)...
摘要:相反,雙向鏈表具有指向其前后元素的節(jié)點(diǎn)。另外,可以對(duì)鏈表進(jìn)行排序。這個(gè)實(shí)用程序方法用于打印鏈表中的節(jié)點(diǎn),僅用于調(diào)試目的。第行將更新為,這是從鏈表中彈出最后一個(gè)元素的行為。如果鏈表為空,則返回。 showImg(https://segmentfault.com/img/bVbsaI7?w=1600&h=228); 什么是鏈表 單鏈表是表示一系列節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu),其中每個(gè)節(jié)點(diǎn)指向鏈表中的下一...
摘要:插入排序維基百科一般來(lái)說(shuō),插入排序都采用在數(shù)組上實(shí)現(xiàn)。在放這個(gè)數(shù)之前,這個(gè)數(shù)的目標(biāo)位置和原始位置之間的數(shù)都要先進(jìn)行后移。最后,當(dāng),即遍歷完整個(gè)原鏈表之后,新鏈表排序完成。 Problem Sort a linked list using insertion sort. Example Given 1->3->2->0->null, return 0->1->2->3->null. No...
摘要:棧被稱為一種后入先出的數(shù)據(jù)結(jié)構(gòu)。散列使用的數(shù)據(jù)結(jié)構(gòu)叫做散列表。這些操作需要求助于其他數(shù)據(jù)結(jié)構(gòu),比如下面介紹的二叉查找樹。 前言 在過(guò)去的幾年中,得益于Node.js的興起,JavaScript越來(lái)越廣泛地用于服務(wù)器端編程。鑒于JavaScript語(yǔ)言已經(jīng)走出了瀏覽器,程序員發(fā)現(xiàn)他們需要更多傳統(tǒng)語(yǔ)言(比如C++和Java)提供的工具。這些工具包括傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)(如鏈表,棧,隊(duì)列,圖等),...
閱讀 3411·2021-11-24 10:30
閱讀 3283·2021-11-22 15:29
閱讀 3715·2021-10-28 09:32
閱讀 1288·2021-09-07 10:22
閱讀 3346·2019-08-30 15:55
閱讀 3632·2019-08-30 15:54
閱讀 3511·2019-08-30 15:54
閱讀 2842·2019-08-30 15:44