摘要：既然說到地址空間了就順帶說一下上面環(huán)形鏈表這道題的另一種很的解法吧。介紹完常規(guī)操作鏈表的一些基本知識(shí)點(diǎn)后，現(xiàn)在回到快慢指針。

??前幾天第一次在 Segmentfault 發(fā)文—JavaScript：十大排序的算法思路和代碼實(shí)現(xiàn)，發(fā)現(xiàn)大家似乎挺喜歡算法的，所以今天再分享一篇前兩個(gè)星期寫的 Leetcode 刷題總結(jié)，希望對(duì)大家能有所幫助。

??本文首發(fā)于我的blog

??今天終于刷完了 Leetcode 上的鏈表專題，雖然只有 31 道題（總共是 35 道，但有 4 道題加了鎖）而已，但也陸陸續(xù)續(xù)做了兩三個(gè)星期，嚴(yán)重跟不上原先計(jì)劃啊。本來打算數(shù)據(jù)結(jié)構(gòu)課程老師講完一個(gè)專題，我就用 JS 在 Leetcode 做一個(gè)專題的。然而老師現(xiàn)在都講到圖了，而我連二叉樹都還沒刷 Orz（附上一張 AC 圖，看著還是挺有成就感的嘛）。

??先寫一篇博客總結(jié)一下這陣子刷鏈表題的收獲吧，有輸入也要有輸出。這里就不花篇幅介紹鏈表的一些基本概念了，不清楚的看官就自行谷歌一下吧，本文主要介紹一些常見的鏈表題和解題思路。文中提到的 Leetcode 題目都有給出題目鏈接以及相關(guān)解題代碼，使用其他方法的解題代碼，或者更多 Leetcode 題解可以訪問我的GitHub 算法倉(cāng)庫(kù)。

??不得不說使用數(shù)組 / map 來緩存鏈表中結(jié)點(diǎn)的信息是解決鏈表題的一大殺器，覆蓋問題的范圍包括但不限于：在鏈表中插入 / 刪除結(jié)點(diǎn)、反向輸出鏈表、鏈表排序、翻轉(zhuǎn)鏈表、合并鏈表等，Leetcode 上 31 道鏈表絕大部分都可以使用這種方法解題。具體實(shí)現(xiàn)思路是先使用一個(gè)數(shù)組或者 map 來存儲(chǔ)鏈表中的結(jié)點(diǎn)信息，比如結(jié)點(diǎn)的數(shù)據(jù)值等，之后根據(jù)題目要求對(duì)數(shù)組進(jìn)行相關(guān)操作后，再重新把數(shù)組元素做為每一個(gè)結(jié)點(diǎn)連接成鏈表返回即可。雖然使用緩存來解鏈表題很 dirty，有違鏈表題的本意，而且空間復(fù)雜度也達(dá)到了 O(n)（即使我們常常用空間來?yè)Q時(shí)間，不過還是能避免就避免吧），但這種方法的確很簡(jiǎn)單易懂，看完題目后幾乎就可以馬上動(dòng)手不加思考地敲代碼一次 AC 了，不像常規(guī)操作那樣需要去考慮到很多邊界情況和結(jié)點(diǎn)指向問題。

??當(dāng)然，并不是很提倡這種解法，這樣就失去了做鏈表題的意義。如果只是一心想要解題 AC 的話那無妨。否則的話我建議可以使用數(shù)組緩存先 AC 一遍題，再使用常規(guī)方法解一次題，我個(gè)人就是這么刷鏈表題的。甚至使用常規(guī)方法的話，你還可以分別使用迭代和遞歸來解題，迭代寫起來比較容易，而遞歸的難點(diǎn)在于把握遞歸邊界和遞歸式，但只要理解清楚了的話，遞歸的代碼寫起來真的很少?。ê竺鏁?huì)說到）。

??先找道題 show the code 吧，不然只是單純的說可能會(huì)半知半解。比如這道反轉(zhuǎn)鏈表 II：反轉(zhuǎn)從位置 m 到 n 的鏈表。如果使用數(shù)組緩存的話，這道題就很容易了。只需要兩次遍歷鏈表，第一次把從 m 到 n 的結(jié)點(diǎn)值緩存到一個(gè)數(shù)組中，第二次遍歷的時(shí)候再替換掉鏈表上 m 到 n 的結(jié)點(diǎn)的值就可以了（是不是很簡(jiǎn)單很清晰啊，如果使用常規(guī)方法的話就復(fù)雜得多了）。實(shí)現(xiàn)代碼如下：

var reverseBetween = function(head, m, n) {
  let arr = [];
  function fn(cur, operator) {
    let index = 1;
    let i = 0;
    while(cur) {
      if(index >= m && index <= n) {
        operator === "get" ?  arr.unshift(cur.val) : cur.val = arr[i++];
      }
      else if(index > n) {
        break;
      }
      index++;
      cur = cur.next;
    }
  }
  // 獲取從 m 到 n 的結(jié)點(diǎn)數(shù)值
  fn(head, "get");
  // 重新賦值
  fn(head, "set");
  return head;
};

??其他的題目例如鏈表排序、結(jié)點(diǎn)值交換等也是大致相同的代碼，使用緩存解題就是這么簡(jiǎn)單。至于上面這題的常規(guī)解法，可以戳這里查看，我已經(jīng)在代碼中標(biāo)注好解題思路了。

??使用緩存來解題的時(shí)候，我們可以使用數(shù)組來存儲(chǔ)信息，也可以使用 map，通常情況下兩者是可以通用的。但因?yàn)?strong>數(shù)組和對(duì)象的下標(biāo)只能是字符串，而 map 的鍵名可以是任意數(shù)據(jù)類型，所以 map 有時(shí)候能做一些數(shù)組無法做到的事。比如當(dāng)我們要存儲(chǔ)的不是結(jié)點(diǎn)值，而是整個(gè)結(jié)點(diǎn)的時(shí)候，這時(shí)候使用數(shù)組就無能為力了。舉個(gè)例子，環(huán)形鏈表：判斷一個(gè)鏈表中是否有環(huán)。先看一下環(huán)形鏈表長(zhǎng)什么樣。

??還是使用緩存的方法，我們?cè)诒闅v鏈表的過程中可以把整個(gè)結(jié)點(diǎn)當(dāng)作鍵名放入到 map 中，并把它標(biāo)記為 true 代表這個(gè)結(jié)點(diǎn)已經(jīng)出現(xiàn)過。同時(shí)邊判斷 map 中以這個(gè)結(jié)點(diǎn)為鍵名的值是否為 true，是的話說明這個(gè)結(jié)點(diǎn)重復(fù)出現(xiàn)了兩次，即這個(gè)鏈表有環(huán)。在這道題中我們是沒辦法用數(shù)組來緩存結(jié)點(diǎn)的，因?yàn)楫?dāng)我們把整個(gè)結(jié)點(diǎn)（一個(gè)對(duì)象）當(dāng)作下標(biāo)放入數(shù)組時(shí)，這個(gè)對(duì)象會(huì)先自動(dòng)轉(zhuǎn)化成字符串[object Object]再作為下標(biāo)，所以這時(shí)候只要鏈表結(jié)點(diǎn)數(shù)量大于等于 2 的話，判斷結(jié)果都會(huì)為 true。使用 map 解題的具體實(shí)現(xiàn)代碼見下。

var hasCycle = function(head) {
  let map = new Map();
  while(head) {
    if(map.get(head) === true) {
      return true;
    }
    else {
      map.set(head, true);   
    }
    head = head.next;
  }
  return false;
}

??Leetcode 上還有一道題充分體現(xiàn)了 map 緩存解題的強(qiáng)大，復(fù)制帶隨機(jī)指針的鏈表：給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)，要求返回這個(gè)鏈表的深拷貝。具體的這里就不再多說了。此外，該題還有一種 O(1) 空間復(fù)雜度，O(n) 時(shí)間復(fù)雜度的解法（來自于《劍指offer》第187頁(yè)）也很值得一學(xué)，推薦大家看看，詳情可以看這里。

??在上面環(huán)形鏈表一題中，如果不使用 map 緩存的話，常規(guī)解法就是使用快慢指針了。指針是 C++ 的概念，JavaScript 中沒有指針的說法，但在 JS 中使用一個(gè)變量也可以同樣達(dá)到 C++ 中指針的效果。先稍微解釋一下我對(duì) C++ 指針的理解吧，具體的知識(shí)點(diǎn)看官可以自行谷歌。在 C++ 中聲明一個(gè)變量，其實(shí)聲明的是一個(gè)內(nèi)存地址，可以通過取址符&來獲取這個(gè)變量的地址空間。而我們可以定義一個(gè)指針變量來指向這個(gè)地址空間，比如int *address = &a。這時(shí)候 address 就是指 a 的地址，而 *addess 則代表對(duì)這個(gè)地址空間進(jìn)行取值，也就是 a 的值了。（既然說到地址空間了就順帶說一下上面環(huán)形鏈表這道題的另一種很 6 的解法吧。利用的是堆的地址是從低到高的，而且鏈表的內(nèi)存是順序申請(qǐng)的，所以如果有環(huán)的話當(dāng)要回到環(huán)的入口的時(shí)候，下一個(gè)結(jié)點(diǎn)的地址就會(huì)小于當(dāng)前結(jié)點(diǎn)的地址! 以此判斷就可以得到鏈表中是否有環(huán)的存在了。不過 JS 中沒有提供獲取變量地址的操作方法，所以這種解法和 JS 是無緣的了。C++ 解法可以戳這里查看。）

??有沒有覺得這很像 JS 的按引用傳遞？之所以說在 JS 中使用一個(gè)變量就可以達(dá)到同樣的效果，這和 JS 是弱語言類型和變量的堆棧存儲(chǔ)方式有關(guān)。因?yàn)?JS 是弱語言類型，所以定義一個(gè)變量它既可以是基本數(shù)據(jù)類型，也可以是對(duì)象數(shù)據(jù)類型。而對(duì)象數(shù)據(jù)類型是將整個(gè)對(duì)象存放在堆中的，存儲(chǔ)在棧中的只是它的訪問地址。所以對(duì)象數(shù)據(jù)類型之間的賦值其實(shí)是地址的賦值，指向堆中同一個(gè)內(nèi)存空間的變量會(huì)牽一發(fā)而動(dòng)全身，只要其中一個(gè)改變了內(nèi)存空間中存儲(chǔ)的值，都會(huì)影響到其他變量對(duì)應(yīng)的值。但如果是改變變量的訪問地址的話，則對(duì)其他變量不會(huì)有任何影響。理解這部分內(nèi)容非常重要，因?yàn)槌Ｒ?guī)的鏈表操作都是基于這些出發(fā)的。舉最基本的鏈表循環(huán)來說明。

let cur = head;
while(cur) {
  cur = cur.next;
}

??上面的幾行代碼是最基本的鏈表循環(huán)過程，其中 head 表示一個(gè)鏈表的頭節(jié)點(diǎn)，是一個(gè)鏈表的入口。cur 表示當(dāng)前循環(huán)到的結(jié)點(diǎn)，當(dāng)鏈表達(dá)到了終點(diǎn)即 cur 為 null 的時(shí)候就結(jié)束了循環(huán)。需要注意的是，每一個(gè)結(jié)點(diǎn)都是一個(gè)對(duì)象，簡(jiǎn)單的鏈表結(jié)點(diǎn)都有兩個(gè)屬性val和next，val代表了當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)值，next則代表了下一個(gè)結(jié)點(diǎn)。而由每個(gè)結(jié)點(diǎn)的next不斷連接起其他的結(jié)點(diǎn)，就構(gòu)成了一個(gè)鏈表。因?yàn)閷?duì)象是按引用傳遞，所以可以在循環(huán)到任意一個(gè)結(jié)點(diǎn)的時(shí)候改變這個(gè)結(jié)點(diǎn)cur的信息，比如改變它的數(shù)據(jù)值或是指向的下一個(gè)結(jié)點(diǎn)，并且這會(huì)隨著修改到原鏈表上去。而改變當(dāng)前的結(jié)點(diǎn)cur，因?yàn)槭侵苯有薷钠湓L問地址，所以并不會(huì)影響到原鏈表。鏈表的常規(guī)操作正是在這一變一不變的基礎(chǔ)上完成的，因此操作鏈表的時(shí)候往往需要一個(gè)輔助鏈表，也就是cur，來修改原鏈表的各個(gè)結(jié)點(diǎn)信息卻不改變整個(gè)鏈表的指向。每次循環(huán)結(jié)束后head還是指向原來的鏈表，而cur則指向了鏈表的末尾null。在這個(gè)過程中，除了最開始把head賦值給cur和最后的return外，幾乎都不需要再操作到head了。

??介紹完常規(guī)操作鏈表的一些基本知識(shí)點(diǎn)后，現(xiàn)在回到快慢指針?？炻羔樒鋵?shí)是利用兩個(gè)變量同時(shí)循環(huán)鏈表，區(qū)別在于一個(gè)的速度快一個(gè)的速度慢。比如慢指針slow的速度是 1，每趟循環(huán)都指向當(dāng)前結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)，即slow = slow.next。而快指針fast的速度可以是 2，每趟循環(huán)都指向當(dāng)前結(jié)點(diǎn)的下下個(gè)結(jié)點(diǎn)，即fast = fast.next.next（使用的時(shí)候需要特別注意fast.next是否為null，否則很可能會(huì)報(bào)錯(cuò)）。現(xiàn)在想象一下，兩個(gè)速度不相同的人在同一個(gè)環(huán)形操場(chǎng)跑步，那么這兩個(gè)人最后是不是一定會(huì)相遇。同樣的道理，一個(gè)環(huán)形鏈表，快慢指針同時(shí)在里面移動(dòng)，那么它們最后也一定會(huì)在鏈表的環(huán)中相遇。所以只要在循環(huán)鏈表的過程中，快慢指針相等了就代表該鏈表中有環(huán)。實(shí)現(xiàn)代碼如下。

var hasCycle = function(head) {
  if(head === null) {
    return false;
  }
  let slow = head;
  let fast = head;
  while(fast !== null && fast.next !== null) {
    slow = slow.next;
    fast = fast.next.next;
    if(slow === fast) {
      return true;
    }
  }
  return false;
};

??除了判斷鏈表中有沒有環(huán)外，快慢指針還可以找出鏈表中環(huán)形的入口。假設(shè) A 是鏈表的入口結(jié)點(diǎn)，B 是環(huán)形的入口結(jié)點(diǎn)，C 是快慢指針的相遇點(diǎn)，x 是 AB 的長(zhǎng)度（也就是 AB 之間的結(jié)點(diǎn)數(shù)量），y 是 BC 的長(zhǎng)度，z 是 CB 的長(zhǎng)度。因?yàn)榭熘羔樢苿?dòng)的距離（x + y）是慢指針移動(dòng)的距離（x + y + z + y）的兩倍（當(dāng)快慢指針相遇時(shí)，快指針比慢指針多移動(dòng)了一圈），所以 z = x。因此，只要在快慢指針相遇的時(shí)候，再讓一個(gè)新指針從頭節(jié)點(diǎn) A 開始移動(dòng)，與此同時(shí)慢指針也繼續(xù)從 C 點(diǎn)移動(dòng)。但新指針和慢指針相遇的時(shí)候，也就是在鏈表環(huán)形的入口處 B。該題的三種實(shí)現(xiàn)代碼可以戳這里查看。

??如果我們把快指針的速度設(shè)置為 2，即每趟循環(huán)都指向當(dāng)前結(jié)點(diǎn)的下下個(gè)結(jié)點(diǎn)。那么快慢指針在移動(dòng)的過程中，快指針移動(dòng)的距離都會(huì)是慢指針移動(dòng)距離的兩倍，利用這個(gè)性質(zhì)我們可以很方便地得到鏈表的中間結(jié)點(diǎn)。只要讓快慢指針同時(shí)從頭節(jié)點(diǎn)開始移動(dòng)，當(dāng)快指針走到鏈表的最后一個(gè)結(jié)點(diǎn)（鏈表長(zhǎng)度是奇數(shù)）或是倒數(shù)第二個(gè)結(jié)點(diǎn)（鏈表長(zhǎng)度是偶數(shù)）的時(shí)候，慢指針就走到了鏈表中點(diǎn)。這里給出題目鏈接和實(shí)現(xiàn)代碼。

var middleNode = function(head) {
  let slow = head;
  let fast = head;
  while(fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;
  }
  return slow;
};

??先后指針和快慢指針很類似，不同的是先后指針的移動(dòng)速度是一樣的，而且兩者并沒有同時(shí)開始移動(dòng)，是一前一后從頭節(jié)點(diǎn)出發(fā)的。先后指針主要用來尋找鏈表中倒數(shù)第 k 個(gè)結(jié)點(diǎn)。通常我們尋找鏈表中倒數(shù)第 k 個(gè)結(jié)點(diǎn)可以有兩種辦法。 一是先循環(huán)一遍鏈表計(jì)算它的長(zhǎng)度n，再正向循環(huán)一遍找到該結(jié)點(diǎn)的位置（正向是第 n - k + 1 個(gè)結(jié)點(diǎn)）。二是使用雙向鏈表，先移動(dòng)到鏈表結(jié)尾處再開始回溯 k 步，但大多時(shí)候給的鏈表都是單向鏈表，這就又需要我們先循環(huán)一遍鏈表給每一個(gè)結(jié)點(diǎn)增加一個(gè)前驅(qū)了。

??使用先后指針的話只需要一趟循環(huán)鏈表，實(shí)現(xiàn)思路是先讓快指針走 k-1 步，再讓慢指針從頭節(jié)點(diǎn)開始走，這樣當(dāng)快指針走到最后一個(gè)結(jié)點(diǎn)的時(shí)候，慢指針就走到了倒數(shù)第 k 個(gè)結(jié)點(diǎn)。解釋一下為什么，假設(shè)鏈表長(zhǎng)度是 n，那么倒數(shù)第 k 個(gè)結(jié)點(diǎn)也就是正數(shù)的第 n - k + 1 個(gè)結(jié)點(diǎn)（不理解的話可以畫一個(gè)鏈表看看就清楚了）。所以只要從頭節(jié)點(diǎn)出發(fā)，走 n - k 步就可以達(dá)到第 n - k + 1 個(gè)結(jié)點(diǎn)了，因此現(xiàn)在的問題就變成了如何控制指針只走 n - k 步。在長(zhǎng)度為 n 的鏈表中，從頭節(jié)點(diǎn)走到最后一個(gè)結(jié)點(diǎn)總共需要走 n - 1 步，所以只要讓快指針先走 (n - 1) - (n - k)= k - 1 步后再讓慢指針從頭節(jié)點(diǎn)出發(fā)，這樣快指針走到最后一個(gè)結(jié)點(diǎn)的時(shí)候慢指針也就走到了倒數(shù)第 n - k + 1 個(gè)結(jié)點(diǎn)。具體實(shí)現(xiàn)代碼如下。

var removeNthFromEnd = function(head, k) {
  let fast = head;
  for(let i=1; i<=k-1; i++) {
    fast = fast.next;
  }
  let slow = head;
  while(fast.next) {
    fast = fast.next;
    slow = slow.next;
  }
  return slow;
}

??Leetcode 上有一道題是對(duì)尋找倒數(shù)第 k 個(gè)結(jié)點(diǎn)的簡(jiǎn)單變形，題目要求是要?jiǎng)h除倒數(shù)第 k 個(gè)結(jié)點(diǎn)。代碼和上面的代碼大致相同，只是要再用到一個(gè)變量pre來存儲(chǔ)倒數(shù)第 k 個(gè)結(jié)點(diǎn)的前一個(gè)結(jié)點(diǎn)，這樣才可以把倒數(shù)第 k 個(gè)結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)連接到pre后面實(shí)現(xiàn)刪除結(jié)點(diǎn)的目的。實(shí)現(xiàn)代碼可以戳這里查看。

??雙向鏈表是在普通的鏈表上給每一個(gè)結(jié)點(diǎn)增加pre屬性來指向它的上一個(gè)結(jié)點(diǎn)，這樣就可以通過某一個(gè)結(jié)點(diǎn)直接找到它的前驅(qū)而不需要專門去緩存了。下面的代碼是把一個(gè)普通的鏈表轉(zhuǎn)化為雙向鏈表。

let pre = null;
let cur = head;
while(cur) {
  cur.pre = pre;
  pre = cur;
  cur = cur.next;
}

??雙向鏈表的應(yīng)用場(chǎng)景還是挺多，比如上例尋找倒數(shù)第 n 個(gè)結(jié)點(diǎn)，或者是判斷回文鏈表。可以使用兩個(gè)指針，從鏈表的首尾一起向鏈表中間移動(dòng)，一邊判斷兩個(gè)指針的數(shù)據(jù)值是否相同。實(shí)現(xiàn)代碼可以戳這里查看。

??除了借助雙向鏈表外，還可以先翻轉(zhuǎn)鏈表得到一個(gè)新的鏈表，再?gòu)念^節(jié)點(diǎn)開始循環(huán)比較兩個(gè)鏈表的數(shù)據(jù)值（當(dāng)然使用數(shù)組緩存也是一種方法）。可能各位看官看到上面這句話覺得沒什么毛病，通過翻轉(zhuǎn)來判斷鏈表 / 字符串 / 數(shù)組是否是回文的也是一個(gè)很常見的解法，但不知道看官有沒有考慮到一個(gè)問題，翻轉(zhuǎn)鏈表是會(huì)修改到原鏈表的，對(duì)后續(xù)循環(huán)鏈表比較兩個(gè)鏈表結(jié)點(diǎn)的數(shù)據(jù)值是有影響的！一發(fā)現(xiàn)了這個(gè)問題，是不是馬上聯(lián)想到了 JS 的深拷貝。沒錯(cuò)，一開始為了解決這個(gè)問題我是直接采用JSON.parse + JSON.stringify來粗暴實(shí)現(xiàn)深拷貝的（反正鏈表中沒有 Date，Symbol 、RegExp、Error、function 以及 null 和 undefined 這些特殊的數(shù)據(jù)），但不知道為什么JSON.parse(JSON.stringify(head))報(bào)了棧溢出的錯(cuò)誤，現(xiàn)在還沒想通原因 Orz。所以只能使用遞歸去深拷貝一次鏈表了，下面給出翻轉(zhuǎn)鏈表和深拷貝鏈表的代碼。

// 翻轉(zhuǎn)鏈表
function reverse(head) {
  let pre = null;
  let cur = head;
  while(cur) {
    let temp = cur.next;
    cur.next = pre;
    pre = cur;
    cur = temp;
  }
  return pre;
}

// 翻轉(zhuǎn)鏈表的遞歸寫法
var reverseList = function(head) {
  if(head === null || head.next === null) {
    return head;
  }
  let cur = reverseList(head.next);
  head.next.next = head
  head.next = null;
  return cur;
}

// 深拷貝鏈表
function deepClone(head) {
  if(head === null)  return null;
  let ans = new ListNode(head.val);
  ans.next = clone(head.next);
  return ans;
}

??回文鏈表的 3 種解題方法（數(shù)組緩存、雙向鏈表、翻轉(zhuǎn)鏈表）可以戳這里查看，題目鏈接在這里。

??除此之外還有一道重排鏈表的題，解題思路和判斷回文鏈表大致相同，各位看官有興趣的話可以試著 AC 這道題。同樣的，這道題我也給出了 3 種解題方法。

??使用遞歸解決鏈表問題不得不說是十分契合的，因?yàn)楹芏噫湵韱栴}都可以分割成幾個(gè)相同的子問題以縮小問題規(guī)模，再通過調(diào)用自身返回局部問題的答案從而來解決大問題的。比如合并有序鏈表，當(dāng)兩個(gè)鏈表長(zhǎng)度都只有 1 的時(shí)候，就是只有判斷頭節(jié)點(diǎn)的數(shù)據(jù)值大小并合并兩者而已。當(dāng)鏈表一長(zhǎng)問題規(guī)模一大，也只需調(diào)用自身來判斷兩者的下一個(gè)結(jié)點(diǎn)和已有序的鏈表，通過不斷遞歸解決小問題最后便能得到大問題的解。

??更多問題例如刪除鏈表中重復(fù)元素、刪除鏈表中的特定值、兩兩交換鏈表結(jié)點(diǎn)等也是可以通過遞歸來解決的，看官有興趣可以自行嘗試 AC，相關(guān)的解決代碼可以在這里找到。使用遞歸解決問題的優(yōu)勢(shì)在于遞歸的代碼十分簡(jiǎn)潔，有時(shí)候使用迭代可能需要十幾二十行的代碼，使用遞歸則只需要短短幾行而已，有沒有覺得很短小精悍啊啊啊。不過遞歸也還是得小心使用，否則一旦遞歸的層次太多很容易導(dǎo)致棧溢出（有沒有聯(lián)想到什么，其實(shí)就是函數(shù)執(zhí)行上下文太多使執(zhí)行棧炸了）。

??有時(shí)候我們?cè)谘h(huán)鏈表進(jìn)行一些判斷的時(shí)候，需要對(duì)頭結(jié)點(diǎn)進(jìn)行特殊判斷，比如要新創(chuàng)建一個(gè)鏈表 newList 并根據(jù)一些條件在上面增加結(jié)點(diǎn)。我們通常是直接使用newList.next來修改結(jié)點(diǎn)指向從而增加結(jié)點(diǎn)的。但第一次添加結(jié)點(diǎn)的時(shí)候，newList 是為空的，不能直接使用newList.next，需要我們對(duì) newList 進(jìn)行判斷看看它是否為空，為空的話就直接對(duì) newList 賦值，不為空再修改newList.next。

??為了避免對(duì)頭節(jié)點(diǎn)進(jìn)行特殊處理，我們可以在 newList 的初始化的時(shí)候先給它一個(gè)頭結(jié)點(diǎn)，比如let newList = new ListNode(0)。這樣在操作過程中只使用newList.next就可以了而不需要另行判斷，而最后結(jié)果只要返回newList.next（當(dāng)然，在循環(huán)的時(shí)候需要使用一個(gè)輔助鏈表來循環(huán) newList ，否則會(huì)改變到 newList 的指向）?？赡苣銜?huì)覺得不就是多了一個(gè)else if判斷嗎，對(duì)代碼也沒多大影響，但如果在這個(gè)if中包含了很多其他相關(guān)操作呢，這樣的話if和else if里就會(huì)有很多代碼是重復(fù)的，不僅代碼量變多了還很冗余耶。

??關(guān)于鏈表本文就說這么多啦，如果大家發(fā)現(xiàn)有什么錯(cuò)誤、或者有什么疑問和補(bǔ)充的，歡迎在下方留言。更多 LeetCode 題目的 JavaScript 解法可以參考我的GitHub算法倉(cāng)庫(kù)，目前已經(jīng) AC 了一百多道題，并持續(xù)更新中。

??如果大家覺得有幫助的話，就點(diǎn)個(gè) star 鼓勵(lì)鼓勵(lì)我吧，蟹蟹大家