用 JavaScript 實(shí)現(xiàn)鏈表操作 - 03 Get Nth Node

syoya 發(fā)布于2019-08-21 14:53 / 1671人閱讀

摘要：獲得鏈表的第個(gè)節(jié)點(diǎn)。需求實(shí)現(xiàn)一個(gè)方法，傳入一個(gè)鏈表和一個(gè)索引，返回索引代表的節(jié)點(diǎn)。遞歸版本假設(shè)函數(shù)定義為，遞歸過(guò)程為當(dāng)為零，直接返回該節(jié)點(diǎn)，否則遞歸調(diào)用。如果循環(huán)結(jié)束還沒(méi)有查到節(jié)點(diǎn)，那肯定是鏈表或者索引不合法，直接拋異常即可。

TL;DR

獲得鏈表的第 N 個(gè)節(jié)點(diǎn)。系列目錄見(jiàn) 前言和目錄。

需求

實(shí)現(xiàn)一個(gè) getNth() 方法，傳入一個(gè)鏈表和一個(gè)索引，返回索引代表的節(jié)點(diǎn)。索引以 0 為起始，第一個(gè)元素索引為 0 ，第二個(gè)為 1 ，以此類推。比如：

getNth(1 -> 2 -> 3 -> null, 0).data === 1
getNth(1 -> 2 -> 3 -> null, 1).data === 2

傳入的索引必須是在效范圍內(nèi)，即 0..length-1 ，如果索引不合法或者鏈表為空都需要拋出異常。

遞歸版本

假設(shè)函數(shù)定義為 getNth(head, idx) ，遞歸過(guò)程為：當(dāng) idx 為零，直接返回該節(jié)點(diǎn)，否則遞歸調(diào)用 getNth(head.next, idx - 1) 。再處理下邊界情況就完成了，代碼如下：

function getNth(head, idx) {
  if (!head || idx < 0) throw "invalid argument"
  if (idx === 0) return head
  return getNth(head.next, idx - 1)
}

循環(huán)版本

我選擇的 for 循環(huán)，這樣方便把邊界情況檢查都放到循環(huán)里去。如果循環(huán)結(jié)束還沒(méi)有查到節(jié)點(diǎn)，那肯定是鏈表或者索引不合法，直接拋異常即可。對(duì)比這兩個(gè)版本和 02 Length & Count 的例子，不難看出循環(huán)可以比遞歸更容易地處理邊界情況，因?yàn)橐恍l件檢查可以寫進(jìn)循環(huán)的頭部，遞歸就得自己寫 if/else 邏輯。

function getNthV2(head, idx) {
  for (let node = head; node && idx >= 0; node = node.next, idx--) {
    if (idx === 0) return node
  }
  throw "invalid argument"
}

參考資料

Codewars Kata
GitHub 的代碼實(shí)現(xiàn)
GitHub 的測(cè)試

云服務(wù)器 GPU云服務(wù)器用javascript操作xml 多鏈表c語(yǔ)言實(shí)現(xiàn) java實(shí)現(xiàn)鏈表插入遍歷c語(yǔ)言實(shí)現(xiàn)鏈表

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/88049.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 。這篇是開(kāi)篇，簡(jiǎn)單描述了一下我寫這個(gè)的目...

BetaRabbit 2019-08-20 12:25 評(píng)論0 收藏0
用 JavaScript 實(shí)現(xiàn)鏈表操作 - 04 Insert Nth Node

摘要：給定一個(gè)鏈表，一個(gè)范圍在內(nèi)的索引號(hào)，和一個(gè)數(shù)據(jù)，這個(gè)函數(shù)會(huì)生成一個(gè)新的節(jié)點(diǎn)并插入到指定的索引位置，并始終返回鏈表的頭。的返回值一定是個(gè)鏈表，我們把它賦值給就行。但這個(gè)例子的邊界情況是返回值不同如果，返回新節(jié)點(diǎn)。 TL;DR 插入第 N 個(gè)節(jié)點(diǎn)。系列目錄見(jiàn) 前言和目錄。需求實(shí)現(xiàn)一個(gè) insertNth() 方法，在鏈表的第 N 個(gè)索引處插入一個(gè)新節(jié)點(diǎn)。 insertNth() 可以...

894974231 2019-08-22 10:50 評(píng)論0 收藏0
leetcode-019-刪除鏈表倒數(shù)第N個(gè)結(jié)點(diǎn)(Remove Nth Node From End

摘要：第題給定一個(gè)鏈表，刪除鏈表的倒數(shù)第個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。因?yàn)?，若有一個(gè)真正的頭結(jié)點(diǎn)，則所有的元素處理方式都一樣。但以第一個(gè)有效元素為頭結(jié)點(diǎn)，就導(dǎo)致算法的不一致，需要單獨(dú)處理第一個(gè)有效元素頭結(jié)點(diǎn)。 leetcode第19題 Given a linked list, remove the n-th node from the end of list and return its h...

brianway 2019-08-23 14:34 評(píng)論0 收藏0
用 JavaScript 實(shí)現(xiàn)鏈表操作 - 11 Alternating Split

摘要：需求實(shí)現(xiàn)一個(gè)函數(shù)，把一個(gè)鏈表切分成兩個(gè)。子鏈表的節(jié)點(diǎn)應(yīng)該是在父鏈表中交替出現(xiàn)的。所以整個(gè)算法的解法就能很容易地用表示。唯一需要考慮的就是在每個(gè)循環(huán)體中判斷節(jié)點(diǎn)該插入哪個(gè)鏈表。也有人使用持續(xù)增長(zhǎng)的配合取余來(lái)做，比如。 TL;DR 把一個(gè)鏈表交替切分成兩個(gè)，系列目錄見(jiàn) 前言和目錄。需求實(shí)現(xiàn)一個(gè) alternatingSplit() 函數(shù)，把一個(gè)鏈表切分成兩個(gè)。子鏈表的節(jié)點(diǎn)應(yīng)該是在父鏈...

jsyzchen 2019-08-20 14:02 評(píng)論0 收藏0
leetcode19 Remove Nth Node From End of List 從鏈表中移除

摘要：雖然時(shí)間復(fù)雜度還是但是顯然我們可以再一次遍歷中完成這個(gè)任務(wù)。現(xiàn)在跳出下標(biāo)的思路，從另一個(gè)角度分析?？炻?jié)點(diǎn)之間的距離始終是。當(dāng)快節(jié)點(diǎn)到達(dá)終點(diǎn)時(shí)，此時(shí)的慢節(jié)點(diǎn)就是所要?jiǎng)h去的節(jié)點(diǎn)。題目要求 Given a linked list, remove the nth node from the end of list and return its head. For example, ...

YPHP 2019-08-14 18:05 評(píng)論0 收藏0