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

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

摘要：遞歸版本尾遞歸很多遞歸沒(méi)辦法自然的寫(xiě)成尾遞歸，本質(zhì)原因是無(wú)法在多次遞歸過(guò)程中維護(hù)共有的變量，這也是循環(huán)的優(yōu)勢(shì)所在。這是因?yàn)殡m然用的，但并沒(méi)有開(kāi)啟尾遞歸優(yōu)化。

TL;DR

為一個(gè)已排序的鏈表去重，考慮到很長(zhǎng)的鏈表，需要尾調(diào)用優(yōu)化。系列目錄見(jiàn) 前言和目錄。

需求

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

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

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

這個(gè)解決方案需要考慮鏈表很長(zhǎng)的情況，遞歸會(huì)造成棧溢出，所以遞歸方案必須用到尾遞歸。

因?yàn)槠拗疲@里并不解釋什么是尾遞歸，想詳細(xì)了解的可以先看看尾調(diào)用的定義。

遞歸版本 - 非尾遞歸

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

因?yàn)檫f歸版本沒(méi)有循環(huán)，所以一次遞歸操作只能減去一個(gè)重復(fù)元素，比如第一次去除 a1 ，第二次去除 a2 。

先看一個(gè)簡(jiǎn)單的遞歸版本，這個(gè)版本遞歸的是 removeDuplicates 自身。先取鏈表的頭結(jié)點(diǎn) head，如果發(fā)現(xiàn)它跟之后的節(jié)點(diǎn)有重復(fù)，就讓 head 指向之后的節(jié)點(diǎn)（減去一個(gè)重復(fù)），然后再把 head 放入下一個(gè)遞歸里。如果沒(méi)有重復(fù)，則遞歸 head 的下一個(gè)節(jié)點(diǎn)，并把結(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
}

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

遞歸版本 - 尾遞歸

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

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)
}

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

如何測(cè)試尾遞歸

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

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

其次我們需要一個(gè)方法來(lái)生成很長(zhǎng)的，隨機(jī)重復(fù)的，生序排列的鏈表，我的寫(xiě)法如下：

// 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
}

然后就可以測(cè)試了，為了方便同時(shí)測(cè)試溢出和不溢出的情況，寫(xiě)個(gè) helper ，這個(gè) helper 簡(jiǎn)單的判斷函數(shù)是否拋出 RangeError 。因?yàn)楹瘮?shù)的邏輯已經(jīng)在之前的測(cè)試中保證了，這里就不測(cè)試結(jié)果是否正確了。

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 })

完整的測(cè)試見(jiàn) GitHub 。

順帶一提，以上兩個(gè)遞歸方案在 Codewars 上都會(huì)棧溢出。這是因?yàn)?Codewars 雖然用的 Node v6 ，但并沒(méi)有開(kāi)啟尾遞歸優(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
}

可以看到，因?yàn)檠h(huán)體外的共有變量 node 和 head ，這個(gè)例子代碼比遞歸版本要簡(jiǎn)單直觀很多。

總結(jié)

循環(huán)和遞歸沒(méi)有孰優(yōu)孰劣，各有合適的場(chǎng)合。這個(gè) kata 就是一個(gè)循環(huán)比遞歸簡(jiǎn)單的例子。另外，尾遞歸因?yàn)橐獋鬟f中間變量，所以寫(xiě)起來(lái)的感覺(jué)會(huì)更類似循環(huán)而不是正常的遞歸思路，這也是為什么我對(duì)大部分 kata 沒(méi)有做尾遞歸的原因 -- 這個(gè)教程的目的是展示遞歸的思路，而尾遞歸有時(shí)候達(dá)不到這一點(diǎn)。

算法相關(guān)的代碼和測(cè)試我都放在 GitHub 上，如果對(duì)你有幫助請(qǐng)幫我點(diǎn)個(gè)贊！

參考資料

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