<ul id="40oyq"></ul>

<tfoot id="40oyq"></tfoot>

用 JavaScript 實現鏈表操作 - 18 Recursive Reverse

DesGemini 發布于2019-08-20 14:35 / 1530人閱讀

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

TL;DR

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

需求

實現函數 reverse() 用遞歸的方式反轉鏈表。例子如下：

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
}

麻煩的地方就在最后，把節點加入鏈表的末尾需要首先遍歷整個鏈表，這無疑非常低效。我們在上一個 kata 的循環里是怎么解決的呢？維護一個 result 變量代表反轉鏈表，然后每次把新節點放到 result 的頭部，同時把新節點當做新的 result ，大概這個樣子：

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

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

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

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

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

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

參考資料

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

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

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

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

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

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

BetaRabbit 2019-08-20 12:25 評論0 收藏0
[Leetcode] Reverse Linked List 鏈表反轉（遞歸與非遞歸）

摘要：代碼描述調轉指針解法非遞歸用三個指針，緊緊相鄰，不斷前進，每次將指向，將指向指向。描述遞歸解法測試結果 Reverse a singly linked list. 代碼ReverseLinkedList.java package list; public class ReverseLinkedList { /** * 描述 Reverse a singly...

RyanHoo 2019-08-15 14:03 評論0 收藏0
用 JavaScript 實現鏈表操作 - 17 Iterative Reverse

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

only_do 2019-08-20 14:33 評論0 收藏0
LeetCode 之 JavaScript 解答第206題 —— 反轉鏈表（Reverse Link

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

zhangfaliang 2019-08-23 17:12 評論0 收藏0
[Leetcode] Add Two Numbers 鏈表數相加

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

Fourierr 2019-08-14 12:18 評論0 收藏0