&emsp;&emsp;鏈表（Linked List）是不同于數組的另一種數據結構，它的存儲單元（即結點或元素）除了包含任意類型的數據之外，還需要包含指向另一個結點的引用，后文會用術語鏈接表示對結點的引用。 &emsp;&emsp;下面會列出鏈表與數組的具體不同： &emsp;&emsp;（1）數組需要一塊連續的內存空間來存儲；而鏈表則恰恰相反，通過指針將零散的內存串聯在一起。 &emsp;&emsp;（2）數組在插入和刪除時，會做數據搬移，其時間復雜度會 O(n)；而鏈表只需考慮相鄰結點的指針變化，因此時間復雜度是 O(1)。 &emsp;&emsp;（3）當隨機訪問第 K 個元素時，數據可根據首地址和索引計算出對應的內存地址，其時間復雜度為 O(1)；而鏈表則需要讓指針依次遍歷鏈接的結點，因此時間復雜度是 O(n)。 &emsp;&emsp;本系列中面試例題來源于[LeetCode](https://leetcode-cn.com/problemset/all/)、《[劍指Offer](https://book.douban.com/subject/27008702/)》等渠道。像下面這樣以“面試題”為前綴的題目，其解法大都來源于《劍指Offer》一書。 &emsp;&emsp;面試題5[替換空格](https://leetcode-cn.com/problems/ti-huan-kong-ge-lcof/)。合并數組，從后往前合并，減少數字移動次數。 ## 一、鏈表結構 &emsp;&emsp;鏈表包含三種最常見的鏈表結構：單鏈表、雙向鏈表和循環鏈表。 **1）單鏈表** &emsp;&emsp;單鏈表的結點結構如下所示，其中next是后繼指針，可鏈接下一個結點。 ~~~ class Node { constructor(key=null) { this.next = null; this.key = key; } } ~~~ &emsp;&emsp;而單鏈表又可以細分為有頭結點的單鏈表和無頭結點的單鏈表，其中頭結點不存儲任何數據，如下圖1所示。 :-:  圖 1 &emsp;&emsp;下面以有頭結點的[單鏈表為例](https://codepen.io/strick/pen/GRoYevm)，演示單鏈表的插入、遍歷和刪除。 ~~~ class List { constructor() { this.header = new Node(); //頭結點 } add(node) { //插入 if (!this.header.next) { this.header.next = node; return; } let current = this.header; while (current.next != null) { current = current.next; } current.next = node; } traverse() { //遍歷 let current = this.header.next; while (current) { console.log(current.key); current = current.next; } } del(node) { //刪除 let current = this.header.next, //當前結點 prev = this.header; //前驅結點 while (current != node) { current = current.next; prev = prev.next; } if (current) { prev.next = current.next; current.next = null; } } } ~~~ &emsp;&emsp;盡管刪除操作的時間復雜度是 O(1)，但遍歷查找是主要的耗時點，復雜度為 O(n)。因為在刪除時需要知道前驅結點，而單鏈表不能直接讀取，只能從頭開始遍歷。 &emsp;&emsp;面試題6[從尾到頭打印鏈表](https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof/)。每經過一個結點，就放到棧中。當遍歷完后，從棧頂輸出。 &emsp;&emsp;面試題18[刪除鏈表的結點](https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof/)。將結點 j 覆蓋結點 i，結點 i 的next指針指向 j 的下一個結點，這樣能避免獲取結點 i 的前置結點。 &emsp;&emsp;面試題52[兩個鏈表的第一個公共結點](https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof/)。分別把兩個鏈接的結點放入兩個棧中，尾結點就是兩個棧的頂部，如果相同就接著比較下一個棧頂，直至找到最后一個相同結點。 **2）雙向鏈表** &emsp;&emsp;雙向鏈表顧名思義包含兩個方向的指針：前驅和后繼，結點結構如下所示。 ~~~ class Node { constructor(key = null) { this.prev = null; this.key = key; this.next = null; } } ~~~ &emsp;&emsp;雙向鏈表比單鏈表要占更多的內存空間，依托用空間換時間的設計思想，雙向鏈表要比單鏈表更加的高效。 &emsp;&emsp;例如之前的刪除，由于已經保存了前驅結點，也就避免了多余的遍歷（[如下所示](https://codepen.io/strick/pen/ExPdMLx)）。當希望在某個結點之前插入結點，雙向鏈表的優勢也很明顯。 ~~~ class List { add(node) { //插入 if (!this.header.next) { this.header.next = node; node.prev = this.header; return; } let current = this.header; while (current.next != null) { current = current.next; } current.next = node; node.prev = current; } del(node) { //刪除 let current = this.header.next; //當前結點 while (current != node) { current = current.next; } if (current) { current.prev.next = current.next; current.next = null; } } } ~~~ **3）循環鏈表** &emsp;&emsp;循環鏈表是一種特殊的單鏈表，它的尾結點的后繼結點是頭結點，適合處理具有環形結構的問題，例如約瑟夫環。 &emsp;&emsp;面試題62[圓圈中最后剩下的數字](https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/)。用環形鏈表模擬圓圈，每刪除一個數字需要 m 步運算，共有 n 個數字，時間復雜度O(mn)。 ## 二、經典例題 **1）單鏈表逆序** &emsp;&emsp;從鏈表的第二個結點開始，把遍歷到的結點插入到頭結點的后面，直至結束，例如head→1→2→3變為 head→3→2→1。 &emsp;&emsp;采用遞歸的方式完成單鏈表的逆序，[如下所示](https://codepen.io/strick/pen/WNrammY)。例題：LeetCode的[206\. 反轉鏈表](https://leetcode-cn.com/problems/reverse-linked-list/)。 ~~~ class List { reverse() { //逆序 this.recursive(this.header.next); } recursive(node) { if (!node) return; const current = node, next = current.next; if (!next) { //頭結點指向逆序后鏈表的第一個結點 this.header.next = current; return; } this.recursive(next); /************************************ * 移動結點 1->2->3，1->2<-3 * 例如Node(2).next.next就是Node(3).next * 巧妙的將Node(3).next鏈接為Node(2) ************************************/ current.next.next = current; current.next = null; } } ~~~ **2）鏈表中環的檢測** &emsp;&emsp;第一種思路是緩存每個經過的結點，每到一個新結點，就判斷當前序列中是否存在，如果存在，就說明訪問過了。 &emsp;&emsp;第二種思路是使用兩個指針，快指針每次前移兩步，慢指針每次前移一步，當兩個指針指向相同結點時，就證明有環，否則就沒有環，[如下所示](https://codepen.io/strick/pen/VweENWQ)。例題：LeetCode的[141\. 環形鏈表](https://leetcode-cn.com/problems/linked-list-cycle/)。 ~~~ class List { isLoop() { //檢測環 let fast = this.header.next, slow = this.header.next; while (fast && fast.next) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; } return false; } } ~~~ **3）合并兩個有序鏈表** &emsp;&emsp;用兩個指針遍歷兩個鏈表，如果head1指向的數據小于head2的，則將head1指向的結點歸入合并后的鏈表中，否則用head2的，[如下所示](https://codepen.io/strick/pen/bGEmJMP)。例題：LeetCode的[21\. 合并兩個有序鏈表](https://leetcode-cn.com/problems/merge-two-sorted-lists/)。 ~~~ function merge(head1, head2) { let cur1 = head1.next, cur2 = head2.next, cur = null, //合并后的尾結點 head = null; //合并后的頭結點 //合并后鏈表的頭結點為第一個結點元素最小的那個鏈表的頭結點 if (cur1.key > cur2.key) { head = head2; cur = cur2; cur2 = cur2.next; } else { head = head1; cur = cur1; cur1 = cur1.next; } //每次找鏈表剩余結點的最小值對應的結點連接到合并后鏈表的尾部 while (cur1 && cur2) { if (cur1.key > cur2.key) { cur.next = cur2; cur = cur2; cur2 = cur2.next; } else { cur.next = cur1; cur = cur1; cur1 = cur1.next; } } //當遍歷完一個鏈表后把另外一個鏈表剩余的結點鏈接到合并后的鏈表后面 if (cur1 != null) cur.next = cur1; if (cur2 != null) cur.next = cur2; return head; } ~~~ **4）找出鏈表倒數第 n 個結點** &emsp;&emsp;使用兩個指針，快指針比慢指針先前移 n 步，然后兩個指針同時移動。當快指針到底后，慢指針的位置就是所要找的結點，[如下所示](https://codepen.io/strick/pen/xxZmxWv)。例題：LeetCode的[劍指 Offer 22. 鏈表中倒數第k個節點](https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/)。 ~~~ class List { findLast(n) { //刪除鏈表倒數第 n 個結點 let slow = null, fast = null; slow = fast = this.header.next; let i = 0; //前移 n 步 while (i < n && fast) { fast = fast.next; i++; } while (fast) { fast = fast.next; slow = slow.next; } return slow; } } ~~~ **5）求鏈表的中間結點** &emsp;&emsp;使用兩個指針一起遍歷鏈表。慢指針每次走一步，快指針每次走兩步。那么當快指針到達鏈表的末尾時，慢指針必然處于中間位置，[如下所示](https://codepen.io/strick/pen/GRoPRPm)。例題：LeetCode的[876\. 鏈表的中間結點](https://leetcode-cn.com/problems/middle-of-the-linked-list/)。 ~~~ class List { middle() { //求鏈表的中間結點 let slow = this.header.next, fast = this.header.next; while (slow && fast && fast.next) { slow = slow.next; fast = fast.next.next; } return slow; } } ~~~ ***** > 原文出處： [博客園-數據結構和算法躬行記](https://www.cnblogs.com/strick/category/1809992.html) 已建立一個微信前端交流群，如要進群，請先加微信號freedom20180706或掃描下面的二維碼，請求中需注明“看云加群”，在通過請求后就會把你拉進來。還搜集整理了一套[面試資料](https://github.com/pwstrick/daily)，歡迎閱讀。  推薦一款前端監控腳本：[shin-monitor](https://github.com/pwstrick/shin-monitor)，不僅能監控前端的錯誤、通信、打印等行為，還能計算各類性能參數，包括 FMP、LCP、FP 等。