用 JavaScript 實現(xiàn)鏈表操作 - 08 Remove Duplicates

Me_Kun 發(fā)布于2019-08-21 15:04 / 2021人閱讀

摘要：遞歸版本尾遞歸很多遞歸沒辦法自然的寫成尾遞歸，本質原因是無法在多次遞歸過程中維護共有的變量，這也是循環(huán)的優(yōu)勢所在。這是因為雖然用的，但并沒有開啟尾遞歸優(yōu)化。

TL;DR

為一個已排序的鏈表去重，考慮到很長的鏈表，需要尾調用優(yōu)化。系列目錄見前言和目錄。

需求

實現(xiàn)一個 removeDuplicates() 函數(shù)，給定一個升序排列過的鏈表，去除鏈表中重復的元素，并返回修改后的鏈表。理想情況下鏈表只應該被遍歷一次。

var list = 1 -> 2 -> 3 -> 3 -> 4 -> 4 -> 5 -> null
removeDuplicates(list) === 1 -> 2 -> 3 -> 4 -> 5 -> null

如果傳入的鏈表為 null 就返回 null 。

這個解決方案需要考慮鏈表很長的情況，遞歸會造成棧溢出，所以遞歸方案必須用到尾遞歸。

因為篇幅限制，這里并不解釋什么是尾遞歸，想詳細了解的可以先看看尾調用的定義。

遞歸版本 - 非尾遞歸

對數(shù)組或者鏈表去重本身是個花樣很多的算法，但如果鏈表是已排序的，解法就單一很多了，因為重復的元素都是相鄰的。假定鏈表為 a -> a1 -> a2 ... aN -> b ，其中 a1 到 aN 都是對 a 的重復，那么去重就是把鏈表變成 a -> b 。

因為遞歸版本沒有循環(huán)，所以一次遞歸操作只能減去一個重復元素，比如第一次去除 a1 ，第二次去除 a2 。

先看一個簡單的遞歸版本，這個版本遞歸的是 removeDuplicates 自身。先取鏈表的頭結點 head，如果發(fā)現(xiàn)它跟之后的節(jié)點有重復，就讓 head 指向之后的節(jié)點（減去一個重復），然后再把 head 放入下一個遞歸里。如果沒有重復，則遞歸 head 的下一個節(jié)點，并把結果指向 head.next 。

function removeDuplicates(head) {
  if (!head) return null

  const nextNode = head.next
  if (nextNode && head.data === nextNode.data) {
    head.next = nextNode.next
    return removeDuplicates(head)
  }

  head.next = removeDuplicates(nextNode)
  return head
}

這個版本只有第一個 return removeDuplicates(head) 處是尾遞歸，最后的 return head 并不是。所以這個解法并不算完全的尾遞歸，但性能并不算差。經我測試可以處理 30000 個節(jié)點的鏈表，但 40000 個就一定會棧溢出。

遞歸版本 - 尾遞歸

很多遞歸沒辦法自然的寫成尾遞歸，本質原因是無法在多次遞歸過程中維護共有的變量，這也是循環(huán)的優(yōu)勢所在。上面例子中的 head.next = removeDuplicates(nextNode) 就是一個典型，我們需要保留 head 這個變量，好在遞歸結束把結果賦值給 head.next 。尾遞歸優(yōu)化的基本思路，就是把共有的變量繼續(xù)傳給下一個遞歸過程，這種做法往往需要用到額外的函數(shù)參數(shù)。下面是一個改變后的尾遞歸版本：

function removeDuplicatesV2(head, prev = null, re = null) {
  if (!head) return re

  re = re || head
  if (prev && prev.data === head.data) {
    prev.next = head.next
  } else {
    prev = head
  }

  return removeDuplicatesV2(head.next, prev, re)
}

我們加了兩個變量 prev 和 re 。prev 代表 head 的前一個節(jié)點，在遞歸過程中我們判斷的是 prev 和 head 是否有重復。為了最后能返回鏈表的頭我們加了 re 這個參數(shù)，它是最后的返回值。re 僅僅指向最開始的 head ，也就是第一次遞歸的鏈表的頭結點。因為這個算法是修改鏈表自身，只要鏈表非空，頭結點作為返回值就是確定的，即使鏈表開頭就有重復，被移除的也是頭結點之后的節(jié)點。

如何測試尾遞歸

首先我們需要一個支持尾遞歸優(yōu)化的環(huán)境。我測試的環(huán)境是 Node v7 。Node 應該是 6.2 之后就支持尾遞歸優(yōu)化，但需要指定 harmony_tailcalls 參數(shù)開啟，默認并不啟動。我用的 Mocha 寫測試，所以把參數(shù)寫在 mocha.opts 里，配置如下：

--use_strict
--harmony_tailcalls
--require test/support/expect.js

其次我們需要一個方法來生成很長的，隨機重復的，生序排列的鏈表，我的寫法如下：

// Usage: buildRandomSortedList(40000)
function buildRandomSortedList(len) {
  let list
  let prevNode
  let num = 1

  for (let i = 0; i < len; i++) {
    const node = new Node(randomBool() ? num++ : num)
    if (!list) {
      list = node
    } else {
      prevNode.next = node
    }
    prevNode = node
  }

  return list
}

function randomBool() {
  return Math.random() >= 0.5
}

然后就可以測試了，為了方便同時測試溢出和不溢出的情況，寫個 helper ，這個 helper 簡單的判斷函數(shù)是否拋出 RangeError 。因為函數(shù)的邏輯已經在之前的測試中保證了，這里就不測試結果是否正確了。

function createLargeListTests(fn, { isOverflow }) {
  describe(`${fn.name} - max stack size exceed test`, () => {
    it(`${isOverflow ? "should NOT" : "should"} be able to handle a big random list.`, () => {
      Error.stackTraceLimit = 10

      expect(() => {
        fn(buildRandomSortedList(40000))
      })[isOverflow ? "toThrow" : "toNotThrow"](RangeError, "Maximum call stack size exceeded")
    })
  })
}

createLargeListTests(removeDuplicates, { isOverflow: true })
createLargeListTests(removeDuplicatesV2, { isOverflow: false })

完整的測試見 GitHub 。

順帶一提，以上兩個遞歸方案在 Codewars 上都會棧溢出。這是因為 Codewars 雖然用的 Node v6 ，但并沒有開啟尾遞歸優(yōu)化。

循環(huán)版本

思路一致，就不贅述了，直接看代碼：

function removeDuplicatesV3(head) {
  for (let node = head; node; node = node.next) {
    while (node.next && node.data === node.next.data) node.next = node.next.next
  }
  return head
}

可以看到，因為循環(huán)體外的共有變量 node 和 head ，這個例子代碼比遞歸版本要簡單直觀很多。

總結

循環(huán)和遞歸沒有孰優(yōu)孰劣，各有合適的場合。這個 kata 就是一個循環(huán)比遞歸簡單的例子。另外，尾遞歸因為要傳遞中間變量，所以寫起來的感覺會更類似循環(huán)而不是正常的遞歸思路，這也是為什么我對大部分 kata 沒有做尾遞歸的原因 -- 這個教程的目的是展示遞歸的思路，而尾遞歸有時候達不到這一點。

算法相關的代碼和測試我都放在 GitHub 上，如果對你有幫助請幫我點個贊！

參考資料

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

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

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

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

LeetCode 攻略 - 2019 年 7 月上半月匯總（55 題攻略）

摘要：微信公眾號記錄截圖記錄截圖目前關于這塊算法與數(shù)據(jù)結構的安排前。已攻略返回目錄目前已攻略篇文章。會根據(jù)題解以及留言內容，進行補充，并添加上提供題解的小伙伴的昵稱和地址。本許可協(xié)議授權之外的使用權限可以從處獲得。 Create by jsliang on 2019-07-15 11:54:45 Recently revised in 2019-07-15 15:25:25 一目錄不...

warmcheng 2019-08-26 10:09 評論0 收藏0
LeetCode 攻略 - 2019 年 7 月下半月匯總（100 題攻略）

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

tain335 2019-08-26 10:28 評論0 收藏0
用 JavaScript 實現(xiàn)鏈表操作 - 前言和目錄

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

BetaRabbit 2019-08-20 12:25 評論0 收藏0
leetcode83 Remove Duplicates from Sorted List從有序鏈表

摘要：題目要求從有序鏈表中刪除重復的數(shù)字，并且返回刪除后的頭結點例如輸入鏈表為返回這題和相似，只是數(shù)據(jù)結構從數(shù)組變成了鏈表若還有更好的思路，請多多指教想要了解更多開發(fā)技術，面試教程以及互聯(lián)網公司內推，歡迎關注我的微信公眾題目要求：從有序鏈表中刪除重復的數(shù)字，并且返回刪除后的頭結點例如輸入鏈表為1->1->2,返回1->2 這題和leetcode26相似，只是數(shù)據(jù)結構從數(shù)組變成了鏈表 /*...

JessYanCoding 2019-08-14 17:52 評論0 收藏0
leetcode82. Remove Duplicates from Sorted List II

摘要：題目要求翻譯將鏈表中重復的元素全部刪除，返回新的頭結點。相比于，這里將重復的元素全部刪除。除此以外，我們還需要知道重復元素的前一個值和重復元素的最后一個值。如果存在重復值，則跳過重復值后，前節(jié)點不變，否則前節(jié)點跟隨后節(jié)點同時向后移動。題目要求 Given a sorted linked list, delete all nodes that have duplicate number...

崔曉明 2019-08-15 10:36 評論0 收藏0