成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

用 JavaScript 實(shí)現(xiàn)鏈表操作 - 18 Recursive Reverse

DesGemini / 1533人閱讀

摘要：需求實(shí)現(xiàn)函數(shù)用遞歸的方式反轉(zhuǎn)鏈表。整理一番后的代碼如下上面這段代碼同時(shí)也是尾遞歸。在遞歸函數(shù)中開額外的參數(shù)很是常見的做法，也是尾遞歸優(yōu)化的必要手段。

TL;DR

用遞歸的方式反轉(zhuǎn)鏈表，系列目錄見 前言和目錄 。

需求

實(shí)現(xiàn)函數(shù) reverse() 用遞歸的方式反轉(zhuǎn)鏈表。例子如下：

var list = 2 -> 1 -> 3 -> 6 -> 5 -> null
reverse(list) === 5 -> 6 -> 3 -> 1 -> 2 -> null
解法

讓我們先思考一下遞歸的大概解法：

function reverse(head) {
  const node = new Node(head.data)
  const rest = reverse(head.next)
  // 把 node 放到 rest 的末尾，并返回 rest
}

麻煩的地方就在最后，把節(jié)點(diǎn)加入鏈表的末尾需要首先遍歷整個(gè)鏈表，這無疑非常低效。我們在上一個(gè) kata 的循環(huán)里是怎么解決的呢？維護(hù)一個(gè) result 變量代表反轉(zhuǎn)鏈表，然后每次把新節(jié)點(diǎn)放到 result 的頭部，同時(shí)把新節(jié)點(diǎn)當(dāng)做新的 result ，大概這個(gè)樣子：

let result
for (let node = list; node; node = node.next) {
  result = new Node(node.data, result)
}

為了在遞歸里達(dá)到同樣的效果，我們也必須維護(hù)這么一個(gè)變量。為了在每次遞歸過程中都能用到這個(gè)變量，我們得把它當(dāng)函數(shù)的參數(shù)傳遞下去，reverse 的函數(shù)簽名就變成這樣：

function reverse(head, acc) { ... }

這里 acc 就是反轉(zhuǎn)的鏈表。整理一番后的代碼如下：

function reverse(head, acc = null) {
  return head ? reverse(head.next, new Node(head.data, acc)) : acc
}

上面這段代碼同時(shí)也是尾遞歸。在遞歸函數(shù)中開額外的參數(shù)很是常見的做法，也是尾遞歸優(yōu)化的必要手段。

參考資料

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

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/81773.html

相關(guān)文章

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

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

    BetaRabbit 評論0 收藏0

  • [Leetcode] Reverse Linked List 鏈表反轉(zhuǎn)（遞歸與非遞歸）

    摘要：代碼描述調(diào)轉(zhuǎn)指針解法非遞歸用三個(gè)指針，緊緊相鄰，不斷前進(jìn)，每次將指向，將指向指向。描述遞歸解法測試結(jié)果 Reverse a singly linked list. 代碼ReverseLinkedList.java package list; public class ReverseLinkedList { /** * 描述 Reverse a singly...

    RyanHoo 評論0 收藏0

  • 用 JavaScript 實(shí)現(xiàn)鏈表操作 - 17 Iterative Reverse

    摘要：需求實(shí)現(xiàn)方法用循環(huán)的方式反轉(zhuǎn)鏈表，鏈表應(yīng)該只遍歷一次。注意這個(gè)函數(shù)直接修改了鏈表本身，所以不需要返回值。解法代碼如下思路是，從前到后遍歷鏈表，對每個(gè)節(jié)點(diǎn)復(fù)制一份，并讓它的指向前一個(gè)節(jié)點(diǎn)。參考資料的代碼實(shí)現(xiàn)的測試 TL;DR 用循環(huán)的方式反轉(zhuǎn)鏈表，系列目錄見 前言和目錄 。 需求 實(shí)現(xiàn)方法 reverse() 用循環(huán)的方式反轉(zhuǎn)鏈表，鏈表應(yīng)該只遍歷一次。注意這個(gè)函數(shù)直接修改了鏈表本身，所以...

    only_do 評論0 收藏0

  • LeetCode 之 JavaScript 解答第206題 —— 反轉(zhuǎn)鏈表（Reverse Link

    摘要：算法思路兩種方法一般反轉(zhuǎn)遞歸法一般解決定義三個(gè)指針，分別為，存儲(chǔ)當(dāng)前結(jié)點(diǎn)，指向反轉(zhuǎn)好的結(jié)點(diǎn)的頭結(jié)點(diǎn)，存儲(chǔ)下一結(jié)點(diǎn)信息。遞歸法重點(diǎn)分析先確定終止條件當(dāng)下一結(jié)點(diǎn)為時(shí)，返回當(dāng)前節(jié)點(diǎn)判斷當(dāng)前的鏈表是否為遞歸找到尾結(jié)點(diǎn)，將其存儲(chǔ)為頭結(jié)點(diǎn)。 Time：2019/4/23Title: Reverse Linked ListDifficulty: EasyAuthor: 小鹿 題目：Reverse...

    zhangfaliang 評論0 收藏0

  • [Leetcode] Add Two Numbers 鏈表數(shù)相加

    摘要：過程同樣是對齊相加，不足位補(bǔ)。迭代終止條件是兩個(gè)都為。如果這是一個(gè)類的話該如何實(shí)現(xiàn)將鏈表或者數(shù)組作為成員變量，提供對其操作的各種方法。 Add Two Numbers You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order a...

    Fourierr 評論0 收藏0

發(fā)表評論

0條評論

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