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

only_do 發(fā)布于2019-08-20 14:33 / 2325人閱讀

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

TL;DR

用循環(huán)的方式反轉(zhuǎn)鏈表，系列目錄見(jiàn) 前言和目錄。

需求

實(shí)現(xiàn)方法 reverse() 用循環(huán)的方式反轉(zhuǎn)鏈表，鏈表應(yīng)該只遍歷一次。注意這個(gè)函數(shù)直接修改了鏈表本身，所以不需要返回值。

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

解法

代碼如下：

function reverse(list) {
  if (!list) return null

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

  list.data = result.data
  list.next = result.next
}

思路是，從前到后遍歷鏈表，對(duì)每個(gè)節(jié)點(diǎn)復(fù)制一份，并讓它的 next 指向前一個(gè)節(jié)點(diǎn)。最后 result 就是一個(gè)反轉(zhuǎn)的新鏈表了。那么如何修改 list 呢？很簡(jiǎn)單，把 result 的首節(jié)點(diǎn)值賦給 list ，然后讓 list 指向 result 的第二個(gè)節(jié)點(diǎn)就行。

參考資料

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

GPU云服務(wù)器云服務(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/81731.html

相關(guān)文章

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

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

BetaRabbit 2019-08-20 12:25 評(píng)論0 收藏0
[Leetcode] Add Two Numbers 鏈表數(shù)相加

摘要：過(guò)程同樣是對(duì)齊相加，不足位補(bǔ)。迭代終止條件是兩個(gè)都為。如果這是一個(gè)類(lèi)的話該如何實(shí)現(xiàn)將鏈表或者數(shù)組作為成員變量，提供對(duì)其操作的各種方法。 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 評(píng)論0 收藏0
用 JavaScript 實(shí)現(xiàn)鏈表操作 - 18 Recursive Reverse

摘要：需求實(shí)現(xiàn)函數(shù)用遞歸的方式反轉(zhuǎn)鏈表。整理一番后的代碼如下上面這段代碼同時(shí)也是尾遞歸。在遞歸函數(shù)中開(kāi)額外的參數(shù)很是常見(jiàn)的做法，也是尾遞歸優(yōu)化的必要手段。 TL;DR 用遞歸的方式反轉(zhuǎn)鏈表，系列目錄見(jiàn) 前言和目錄。需求實(shí)現(xiàn)函數(shù) reverse() 用遞歸的方式反轉(zhuǎn)鏈表。例子如下： var list = 2 -> 1 -> 3 -> 6 -> 5 -> null reverse(list...

DesGemini 2019-08-20 14:35 評(píng)論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 2019-08-23 17:12 評(píng)論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

摘要：月下半旬攻略道題，目前已攻略題。目前簡(jiǎn)單難度攻略已經(jīng)到題，所以后面會(huì)調(diào)整自己，在刷算法與數(shù)據(jù)結(jié)構(gòu)的同時(shí)，攻略中等難度的題目。 Create by jsliang on 2019-07-30 16:15:37 Recently revised in 2019-07-30 17:04:20 7 月下半旬攻略 45 道題，目前已攻略 100 題。一目錄不折騰的前端，和咸魚(yú)有什么區(qū)別...

tain335 2019-08-26 10:28 評(píng)論0 收藏0