国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

用 JavaScript 實(shí)現(xiàn)鏈表操作 - 10 Move Node In-place

CNZPH / 2031人閱讀

摘要:需求實(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ù)制代碼

  1. var source = 1 -> 2 -> 3 -> null
  2. var dest = 4 -> 5 -> 6 -> null
  3. moveNode(source, dest)
  4. source === 2 -> 3 -> null
  5. 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ù)制代碼

  1. function moveNode(source, dest) {
  2. if (!source || !dest || source.data === null) throw new Error("invalid arguments")
  3. const data = source.data
  4. if (source.next) {
  5. source.data = source.next.data
  6. source.next = source.next.next
  7. } else {
  8. source.data = null
  9. }
  10. if (dest.data === null) {
  11. dest.data = data
  12. } else {
  13. dest.next = new Node(dest.data, dest.next)
  14. dest.data = data
  15. }
  16. }
遞歸方案

這是我最開始思考的方案,差別在于對(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ù)制代碼

  1. function moveNodeV2(source, dest) {
  2. if (source === null || dest === null || source.isEmpty()) {
  3. throw new Error("invalid arguments")
  4. }
  5. pushInPlaceV2(dest, source.data)
  6. if (source.next) {
  7. source.data = source.next.data
  8. source.next = source.next.next
  9. } else {
  10. source.data = null
  11. }
  12. }
  13. function pushInPlaceV2(head, data) {
  14. if (!head) return new Node(data)
  15. if (!head.isEmpty()) head.next = pushInPlaceV2(head.next, head.data)
  16. head.data = data
  17. return head
  18. }
總結(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

相關(guān)文章

  • JavaScript 實(shí)現(xiàn)鏈表操作 - 前言和目錄

    摘要:我打算寫一個(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è)的目...

    BetaRabbit 評(píng)論0 收藏0
  • JavaScript 實(shí)現(xiàn)鏈表操作 - 09 Move Node

    摘要:需求實(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í)...

    suosuopuo 評(píng)論0 收藏0
  • JavaScript 實(shí)現(xiàn)鏈表

    摘要:相反,雙向鏈表具有指向其前后元素的節(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)指向鏈表中的下一...

    appetizerio 評(píng)論0 收藏0
  • [LintCode] Insertion Sort List

    摘要:插入排序維基百科一般來(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...

    wzyplus 評(píng)論0 收藏0
  • JavaScript數(shù)據(jù)結(jié)構(gòu)和算法

    摘要:棧被稱為一種后入先出的數(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ì)列,圖等),...

    EastWoodYang 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<