用 JavaScript 實現鏈表操作 - 02 Length & Count

Batkid 發布于2019-08-22 10:47 / 1031人閱讀

摘要：計算鏈表的長度和指定元素的重復次數。需求實現一個函數來計算鏈表的長度。遞歸版本遞歸是最有表達力的版本。注意因為要在外部作為返回值使用，我們只能用而不是聲明變量。參考資料的代碼實現的測試

TL;DR

計算鏈表的長度和指定元素的重復次數。系列目錄見前言和目錄。

需求

實現一個 length() 函數來計算鏈表的長度。

length(null) === 0
length(1 -> 2 -> 3 -> null) === 3

實現一個 count() 函數來計算指定數字在鏈表中的重復次數。

count(null, 1) === 0
count(1 -> 2 -> 3 -> null, 1) === 1
count(1 -> 1 -> 1 -> 2 -> 2 -> 2 -> 2 -> 3 -> 3 -> null, 2) === 4

length 遞歸版本

遞歸是最有表達力的版本。思路非常簡單。每個鏈表的長度 length(head) 都等于 1 + length(head.next) ?？真湵黹L度為 0 。

function length(head) {
  return head ? 1 + length(head.next) : 0
}

循環版本 - while

鏈表循環第一反應是用 while (node) { node = node.next } 來做，循環外維護一個變量，每次自增 1 即可。

function lengthV2(head) {
  let len = 0
  let node = head

  while (node) {
    len++
    node = node.next
  }

  return len
}

循環版本 - for

for 和 while 在任何情況下都是可以互換的。我們可以用 for 循環把變量初始化，節點后移的操作都放到一起，簡化一下代碼量。注意因為 len 要在 for 外部作為返回值使用，我們只能用 var 而不是 let/const 聲明變量。

function lengthV3(head) {
  for (var len = 0, node = head; node; node = node.next) len++
  return len
}

count 遞歸版本

跟 length 思路類似，區別只是遞歸時判斷一下節點數據。

function count(head, data) {
  if (!head) return 0
  return (head.data === data ? 1 : 0) + count(head.next, data)
}

循環版本

這里我直接演示的 for 版本，思路類似就不多說了。

function countV2(head, data) {
  for (var n = 0, node = head; node; node = node.next) {
    if (node.data === data) n++
  }
  return n
}

參考資料

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

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

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

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

用 JavaScript 實現鏈表操作 - 01 Push &amp; Build List

摘要：寫兩個幫助函數來創建鏈表。用于把一個節點插入到鏈表的頭部。這個方法應該始終返回一個新的鏈表。接收一個數組為參數，創建對應的鏈表。參考資料的代碼實現的測試 TL;DR 寫兩個幫助函數來創建鏈表。系列目錄見前言和目錄。需求寫兩個方法 push 和 buildList 來初始化鏈表。嘗試在 buildList 中使用 push 。下面的例子中我用 a -> b -> c 來表示鏈表，...

Scorpion 2019-08-20 12:35 評論0 收藏0
用 JavaScript 實現鏈表操作 - 03 Get Nth Node

摘要：獲得鏈表的第個節點。需求實現一個方法，傳入一個鏈表和一個索引，返回索引代表的節點。遞歸版本假設函數定義為，遞歸過程為當為零，直接返回該節點，否則遞歸調用。如果循環結束還沒有查到節點，那肯定是鏈表或者索引不合法，直接拋異常即可。 TL;DR 獲得鏈表的第 N 個節點。系列目錄見前言和目錄。需求實現一個 getNth() 方法，傳入一個鏈表和一個索引，返回索引代表的節點。索引以 0...

syoya 2019-08-21 14:53 評論0 收藏0
【譯】JavaScript數據結構（3）：單向鏈表與雙向鏈表

摘要：計算機科學中最常見的兩種數據結構是單鏈表和雙鏈表。雙向鏈表雙向鏈表具有單鏈表的所有功能，并將其擴展為在鏈表中可以進行雙向遍歷。雙向鏈表的操作我們的鏈表將包括兩個構造函數和。與單鏈表不同，雙向鏈表包含對鏈表開頭和結尾節點的引用。翻譯：瘋狂的技術宅英文：https://code.tutsplus.com/art...說明：本文翻譯自系列文章《Data Structures With Ja...

Chiclaim 2019-08-20 18:20 評論0 收藏0
詳解ahooks解決React閉包問題方法

　　想必大家都能看得懂的源碼 ahooks 整體架構篇，且可以使用插件化機制優雅的封裝你的請求hook，現在我們就探討下ahooks 是怎么解決 React 的閉包問題的？?！　eact 的閉包問題　　先來看一個例子：　　importReact,{useState,useEffect}from"react"; 　　exportdefault()=>{ 　　const[c...

3403771864 2022-11-06 16:51 評論0 收藏0
Map總結，看這篇就夠了

摘要：繼承于，實現了接口。的定義的定義從中，我們可以看出和都實現了接口。指向的的總的大小是迭代器還是枚舉類的標志為，表示它是迭代器否則，是枚舉類。默認加載因子指定容量大小的構造函數當的實際容量閾值時，閾值總的容量加載因子，就將的容量翻倍。概要學完了Map的全部內容，我們再回頭開開Map的框架圖。showImg(https://segmentfault.com/img/remote/146...

yzzz 2019-08-15 17:49 評論0 收藏0