用 JavaScript 實現鏈表操作 - 10 Move Node In-place

CNZPH 發布于2019-08-20 13:37 / 2027人閱讀

摘要：需求實現一個函數，把源鏈表的頭結點移到目標鏈表的開頭。要求是不能修改兩個鏈表的引用。跟前一個不同的是，這個是在不改變引用的情況下修改兩個鏈表自身。最優的方案這個算法考的是對鏈表節點的插入和刪除。大致思路為對做刪除一個節點的操作。

TL;DR

用 in-place 的方式把一個鏈表的首節點移到另一個鏈表（不改變鏈表的引用），系列目錄見前言和目錄。

需求

實現一個 moveNode() 函數，把源鏈表的頭結點移到目標鏈表的開頭。要求是不能修改兩個鏈表的引用。

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

當碰到以下的情況應該拋出異常：

源鏈表為 null

目標鏈表為 null

源鏈表是空節點，data 屬性為 null 的節點定義為空節點。

跟前一個 kata 不同的是，這個 kata 是在不改變引用的情況下修改兩個鏈表自身。因此 moveNode() 函數不需要返回值。同時這個 kata 也提出了 空節點 的概念。空節點會用于目標鏈表為空的情況（為了保持引用），在函數執行之后，目標鏈表會由空節點變成一個包含一個節點的鏈表。

你可以使用第一個 kata 的 push 方法。

最優的方案

這個算法考的是對鏈表節點的插入和刪除。基本只對 source 和 dest 分別做一次操作，所以不用區分遞歸和循環。大致思路為：

對 source 做刪除一個節點的操作。如果只有一個節點就直接置空。如果有多個節點，就把第二個節點的值賦給頭節點，然后讓頭結點指向第三個節點。

對 dest 做插入一個節點的操作。如果頭結點為空就直接賦值，否則把頭結點復制一份，作為第二個節點插入到鏈表中，再把新值賦給頭結點。

代碼如下：

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
  }
}

遞歸方案

這是我最開始思考的方案，差別在于對 dest 如何插入新節點的處理上用了遞歸。思路是把所有節點的 data 往后移一位，即把新值賦給第一個節點，第一個節點的值賦給第二個節點，第二個節點的值賦給第三個節點，以此類推。但實際操作中的順序必須是反的，就是把倒數第二個節點的值賦給最后一個節點，倒數第三個節點的值賦給倒數第二個節點…… 這個思路對 dest 操作了 N 次，不如上一個解法的 1 次操作高效。不過也算是個有意思的遞歸用例，所以我仍然把它放了上來。

代碼如下，主要看 pushInPlaceV2 ：

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
}

總結

總是使用遞歸會產生慣性，導致忽略了數據結構的基本特性。鏈表的特性就是插入和刪除的便利，改改引用就成了。

算法相關的代碼和測試我都放在 GitHub 上，如果對你有幫助請幫我點個贊！

參考資料

Codewars Kata
GitHub 的代碼實現
GitHub 的測試

GPU云服務器云服務器用javascript操作xml 多鏈表c語言實現 java實現鏈表插入遍歷c語言實現鏈表

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/81149.html

用 JavaScript 實現鏈表操作 - 前言和目錄

摘要：我打算寫一個鏈表操作的系列，來自的系列，實現語言是。通過自己實現一個鏈表和常用操作，可以加深理解這類數據結構的優缺點。鏈表經常用來訓練指針操作，雖然這只對適用，但等高級語言中控制引用的思路其實也差不多。 TL;DR 我打算寫一個鏈表操作的系列，來自 Codewars 的 Linked List 系列 kata ，實現語言是 JavaScript 。這篇是開篇，簡單描述了一下我寫這個的目...

BetaRabbit 2019-08-20 12:25 評論0 收藏0
用 JavaScript 實現鏈表操作 - 09 Move Node

摘要：需求實現一個函數，把源鏈表的頭節點移到目標鏈表。當源鏈表為空時函數應拋出異常。為了簡化起見，我們會用一個對象來存儲改變后的源鏈表和目標鏈表的引用。它也是函數的返回值。解法配合，這個非常簡單，注意這個函數沒有改變兩個鏈表本身。 TL;DR 把一個鏈表的首節點移到另一個鏈表。系列目錄見前言和目錄。需求實現一個 moveNode() 函數，把源鏈表的頭節點移到目標鏈表。當源鏈表為空時...

suosuopuo 2019-08-20 13:35 評論0 收藏0
用 JavaScript 實現鏈表

摘要：相反，雙向鏈表具有指向其前后元素的節點。另外，可以對鏈表進行排序。這個實用程序方法用于打印鏈表中的節點，僅用于調試目的。第行將更新為，這是從鏈表中彈出最后一個元素的行為。如果鏈表為空，則返回。 showImg(https://segmentfault.com/img/bVbsaI7?w=1600&h=228); 什么是鏈表單鏈表是表示一系列節點的數據結構，其中每個節點指向鏈表中的下一...

appetizerio 2019-08-26 13:51 評論0 收藏0
[LintCode] Insertion Sort List

摘要：插入排序維基百科一般來說，插入排序都采用在數組上實現。在放這個數之前，這個數的目標位置和原始位置之間的數都要先進行后移。最后，當，即遍歷完整個原鏈表之后，新鏈表排序完成。 Problem Sort a linked list using insertion sort. Example Given 1->3->2->0->null, return 0->1->2->3->null. No...

wzyplus 2019-08-14 15:21 評論0 收藏0
JavaScript數據結構和算法

摘要：棧被稱為一種后入先出的數據結構。散列使用的數據結構叫做散列表。這些操作需要求助于其他數據結構，比如下面介紹的二叉查找樹。前言在過去的幾年中，得益于Node.js的興起，JavaScript越來越廣泛地用于服務器端編程。鑒于JavaScript語言已經走出了瀏覽器，程序員發現他們需要更多傳統語言（比如C++和Java）提供的工具。這些工具包括傳統的數據結構（如鏈表，棧，隊列，圖等），...

EastWoodYang 2019-08-21 16:23 評論0 收藏0