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

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

??本文首發于我的blog

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

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

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

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

??先找道題 show the code 吧，不然只是單純的說可能會半知半解。比如這道反轉鏈表 II：反轉從位置 m 到 n 的鏈表。如果使用數組緩存的話，這道題就很容易了。只需要兩次遍歷鏈表，第一次把從 m 到 n 的結點值緩存到一個數組中，第二次遍歷的時候再替換掉鏈表上 m 到 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 的結點數值
  fn(head, "get");
  // 重新賦值
  fn(head, "set");
  return head;
};

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

??使用緩存來解題的時候，我們可以使用數組來存儲信息，也可以使用 map，通常情況下兩者是可以通用的。但因為數組和對象的下標只能是字符串，而 map 的鍵名可以是任意數據類型，所以 map 有時候能做一些數組無法做到的事。比如當我們要存儲的不是結點值，而是整個結點的時候，這時候使用數組就無能為力了。舉個例子，環形鏈表：判斷一個鏈表中是否有環。先看一下環形鏈表長什么樣。

??還是使用緩存的方法，我們在遍歷鏈表的過程中可以把整個結點當作鍵名放入到 map 中，并把它標記為 true 代表這個結點已經出現過。同時邊判斷 map 中以這個結點為鍵名的值是否為 true，是的話說明這個結點重復出現了兩次，即這個鏈表有環。在這道題中我們是沒辦法用數組來緩存結點的，因為當我們把整個結點（一個對象）當作下標放入數組時，這個對象會先自動轉化成字符串[object Object]再作為下標，所以這時候只要鏈表結點數量大于等于 2 的話，判斷結果都會為 true。使用 map 解題的具體實現代碼見下。

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 上還有一道題充分體現了 map 緩存解題的強大，復制帶隨機指針的鏈表：給定一個鏈表，每個節點包含一個額外增加的隨機指針，該指針可以指向鏈表中的任何節點或空節點，要求返回這個鏈表的深拷貝。具體的這里就不再多說了。此外，該題還有一種 O(1) 空間復雜度，O(n) 時間復雜度的解法（來自于《劍指offer》第187頁）也很值得一學，推薦大家看看，詳情可以看這里。

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

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

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

??上面的幾行代碼是最基本的鏈表循環過程，其中 head 表示一個鏈表的頭節點，是一個鏈表的入口。cur 表示當前循環到的結點，當鏈表達到了終點即 cur 為 null 的時候就結束了循環。需要注意的是，每一個結點都是一個對象，簡單的鏈表結點都有兩個屬性val和next，val代表了當前結點的數據值，next則代表了下一個結點。而由每個結點的next不斷連接起其他的結點，就構成了一個鏈表。因為對象是按引用傳遞，所以可以在循環到任意一個結點的時候改變這個結點cur的信息，比如改變它的數據值或是指向的下一個結點，并且這會隨著修改到原鏈表上去。而改變當前的結點cur，因為是直接修改其訪問地址，所以并不會影響到原鏈表。鏈表的常規操作正是在這一變一不變的基礎上完成的，因此操作鏈表的時候往往需要一個輔助鏈表，也就是cur，來修改原鏈表的各個結點信息卻不改變整個鏈表的指向。每次循環結束后head還是指向原來的鏈表，而cur則指向了鏈表的末尾null。在這個過程中，除了最開始把head賦值給cur和最后的return外，幾乎都不需要再操作到head了。

??介紹完常規操作鏈表的一些基本知識點后，現在回到快慢指針。快慢指針其實是利用兩個變量同時循環鏈表，區別在于一個的速度快一個的速度慢。比如慢指針slow的速度是 1，每趟循環都指向當前結點的下一個結點，即slow = slow.next。而快指針fast的速度可以是 2，每趟循環都指向當前結點的下下個結點，即fast = fast.next.next（使用的時候需要特別注意fast.next是否為null，否則很可能會報錯）。現在想象一下，兩個速度不相同的人在同一個環形操場跑步，那么這兩個人最后是不是一定會相遇。同樣的道理，一個環形鏈表，快慢指針同時在里面移動，那么它們最后也一定會在鏈表的環中相遇。所以只要在循環鏈表的過程中，快慢指針相等了就代表該鏈表中有環。實現代碼如下。

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

??除了判斷鏈表中有沒有環外，快慢指針還可以找出鏈表中環形的入口。假設 A 是鏈表的入口結點，B 是環形的入口結點，C 是快慢指針的相遇點，x 是 AB 的長度（也就是 AB 之間的結點數量），y 是 BC 的長度，z 是 CB 的長度。因為快指針移動的距離（x + y）是慢指針移動的距離（x + y + z + y）的兩倍（當快慢指針相遇時，快指針比慢指針多移動了一圈），所以 z = x。因此，只要在快慢指針相遇的時候，再讓一個新指針從頭節點 A 開始移動，與此同時慢指針也繼續從 C 點移動。但新指針和慢指針相遇的時候，也就是在鏈表環形的入口處 B。該題的三種實現代碼可以戳這里查看。

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

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

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

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

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 上有一道題是對尋找倒數第 k 個結點的簡單變形，題目要求是要刪除倒數第 k 個結點。代碼和上面的代碼大致相同，只是要再用到一個變量pre來存儲倒數第 k 個結點的前一個結點，這樣才可以把倒數第 k 個結點的下一個結點連接到pre后面實現刪除結點的目的。實現代碼可以戳這里查看。

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

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

??雙向鏈表的應用場景還是挺多，比如上例尋找倒數第 n 個結點，或者是判斷回文鏈表。可以使用兩個指針，從鏈表的首尾一起向鏈表中間移動，一邊判斷兩個指針的數據值是否相同。實現代碼可以戳這里查看。

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

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

// 翻轉鏈表的遞歸寫法
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 種解題方法（數組緩存、雙向鏈表、翻轉鏈表）可以戳這里查看，題目鏈接在這里。

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

??使用遞歸解決鏈表問題不得不說是十分契合的，因為很多鏈表問題都可以分割成幾個相同的子問題以縮小問題規模，再通過調用自身返回局部問題的答案從而來解決大問題的。比如合并有序鏈表，當兩個鏈表長度都只有 1 的時候，就是只有判斷頭節點的數據值大小并合并兩者而已。當鏈表一長問題規模一大，也只需調用自身來判斷兩者的下一個結點和已有序的鏈表，通過不斷遞歸解決小問題最后便能得到大問題的解。

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

??有時候我們在循環鏈表進行一些判斷的時候，需要對頭結點進行特殊判斷，比如要新創建一個鏈表 newList 并根據一些條件在上面增加結點。我們通常是直接使用newList.next來修改結點指向從而增加結點的。但第一次添加結點的時候，newList 是為空的，不能直接使用newList.next，需要我們對 newList 進行判斷看看它是否為空，為空的話就直接對 newList 賦值，不為空再修改newList.next。

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

??關于鏈表本文就說這么多啦，如果大家發現有什么錯誤、或者有什么疑問和補充的，歡迎在下方留言。更多 LeetCode 題目的 JavaScript 解法可以參考我的GitHub算法倉庫，目前已經 AC 了一百多道題，并持續更新中。

??如果大家覺得有幫助的話，就點個 star 鼓勵鼓勵我吧，蟹蟹大家