前端算法系統(tǒng)練習(xí)之怎么掌握鏈表

這篇文章主要講解了“前端算法系統(tǒng)練習(xí)之怎么掌握鏈表”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“前端算法系統(tǒng)練習(xí)之怎么掌握鏈表”吧！

在練習(xí)之前，首先闡明一下我的觀點(diǎn)，以免大家對(duì)數(shù)據(jù)結(jié)構(gòu)和算法或者這個(gè)系列產(chǎn)生更多的誤解。

我想各位當(dāng)中肯定有準(zhǔn)備面試的同學(xué)，那么你肯定聽(tīng)說(shuō)過(guò)面試造火箭，工作擰螺絲, 不少人也拿這句話拿來(lái)詬病當(dāng)前一些互聯(lián)網(wǎng)大廠的算法面試，因此就有這樣的言論:  除了應(yīng)付面試，學(xué)算法其實(shí)沒(méi)啥用。

這句話我并不完全反對(duì)，因?yàn)楝F(xiàn)在隨著技術(shù)生態(tài)的發(fā)展，各位走在領(lǐng)域前沿的大牛們已經(jīng)給大家備足了輪子，遇到一般的業(yè)務(wù)問(wèn)題直接把人家的方案拿到用就可以了，另外我也看到過(guò)一句話，剛開(kāi)始覺(jué)得扯淡，后來(lái)想想覺(jué)得有那么一絲道理:

凡是需要跨過(guò)一定智商門檻才能掌握的技術(shù)，都不會(huì)輕易的流行。

換句話說(shuō)：技術(shù)變得更簡(jiǎn)單，別人更愿意用，更容易流行。

這也是當(dāng)前各種技術(shù)框架的真實(shí)寫照: 足夠好用，足夠簡(jiǎn)單，簡(jiǎn)單到你不需要知道底層復(fù)雜的細(xì)節(jié)。

那么問(wèn)題來(lái)了，作為一個(gè)集智慧和才華于一身的程序員，自己的價(jià)值在哪里?

我覺(jué)得價(jià)值的大小取決于你能夠解決的問(wèn)題，如果說(shuō)照著設(shè)計(jì)稿畫出一個(gè)簡(jiǎn)單的  Button，你能完成，別的前端也能完成，甚至后后端的同學(xué)都能把效果差不多做出來(lái)，那這個(gè)時(shí)候就談何個(gè)人價(jià)值?只不過(guò)在一個(gè)隨時(shí)可替代的崗位上完成了大多數(shù)人能輕易做到的事情，張三來(lái)完成，或者李四來(lái)完成，其實(shí)沒(méi)什么區(qū)別。

但是現(xiàn)在如果面對(duì)的是一個(gè)復(fù)雜的工程問(wèn)題，需要你來(lái)開(kāi)發(fā)一個(gè)輔助業(yè)務(wù)的腳手架工具，改造框架源碼來(lái)提高項(xiàng)目的擴(kuò)展性，或者面對(duì)嚴(yán)重的性能問(wèn)題能馬上分析出原因，然后給出解決的思路并在不同因素中平衡，這些都不是一個(gè)業(yè)余的玩家能夠在短時(shí)間內(nèi)勝任的，這就是體現(xiàn)自己價(jià)值的地方。

回到算法本身，它代表的是你解決更加復(fù)雜問(wèn)題能力的一部分。所以從長(zhǎng)期來(lái)看，對(duì)我們的發(fā)展是有潛移默化的幫助的。我們接下來(lái)進(jìn)入到鏈表的部分。主要分為下面這幾個(gè)主題:

反轉(zhuǎn)鏈表

反轉(zhuǎn)鏈表這里一共有三個(gè)題目供大家訓(xùn)練。分別是原地單鏈表的反轉(zhuǎn)、兩個(gè)一組反轉(zhuǎn)鏈表和K個(gè)一組反轉(zhuǎn)鏈表，難度由階梯式上升。

而在面試當(dāng)中凡是遇到鏈表，反轉(zhuǎn)類的題目出現(xiàn)的頻率也是數(shù)一數(shù)二的，因此把它當(dāng)做鏈表開(kāi)篇的訓(xùn)練類型，希望大家能引起足夠的重視?。

NO.1 簡(jiǎn)單的反轉(zhuǎn)鏈表

反轉(zhuǎn)一個(gè)單鏈表。

示例:

輸入: 1->2->3->4->5->NULL 輸出: 5->4->3->2->1->NULL

來(lái)源: LeetCode 第 206 題

循環(huán)解決方案

這道題是鏈表中的經(jīng)典題目，充分體現(xiàn)鏈表這種數(shù)據(jù)結(jié)構(gòu)操作思路簡(jiǎn)單, 但是實(shí)現(xiàn)上并沒(méi)有那么簡(jiǎn)單的特點(diǎn)。

那在實(shí)現(xiàn)上應(yīng)該注意一些什么問(wèn)題呢?

保存后續(xù)節(jié)點(diǎn)。作為新手來(lái)說(shuō)，很容易將當(dāng)前節(jié)點(diǎn)的  next指針直接指向前一個(gè)節(jié)點(diǎn)，但其實(shí)當(dāng)前節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)的指針也就丟失了。因此，需要在遍歷的過(guò)程當(dāng)中，先將下一個(gè)節(jié)點(diǎn)保存，然后再操作next指向。

鏈表結(jié)構(gòu)聲定義如下:

function ListNode(val) {   this.val = val;   this.next = null; }

實(shí)現(xiàn)如下:

/**  * @param {ListNode} head  * @return {ListNode}  */ let reverseList =  (head) => {     if (!head)         return null;     let pre = null, cur = head;     while (cur) {         // 關(guān)鍵: 保存下一個(gè)節(jié)點(diǎn)的值         let next = cur.next;         cur.next = pre;         pre = cur;         cur = next;     }     return pre; };

由于邏輯比較簡(jiǎn)單，代碼直接一氣呵成。不過(guò)僅僅寫完還不夠，對(duì)于鏈表問(wèn)題，邊界檢查的習(xí)慣能幫助我們進(jìn)一步保證代碼的質(zhì)量。具體來(lái)說(shuō):

• 當(dāng) head 節(jié)點(diǎn)為空時(shí)，我們已經(jīng)處理，通過(guò)?

• 當(dāng)鏈表只包含一個(gè)節(jié)點(diǎn)時(shí), 此時(shí)我們希望直接返回這個(gè)節(jié)點(diǎn)，對(duì)上述代碼而言，進(jìn)入循環(huán)后 pre 被賦值為cur，也就是head，沒(méi)毛病，通過(guò)?

運(yùn)行在 LeetCode, 成功 AC ?

但作為系統(tǒng)性的訓(xùn)練而言，單單讓程序通過(guò)未免太草率了，我們后續(xù)會(huì)盡可能地用不同的方式去解決相同的問(wèn)題，達(dá)到融會(huì)貫通的效果，也是對(duì)自己思路的開(kāi)拓，有時(shí)候或許能達(dá)到更優(yōu)解。

遞歸解決方案

由于之前的思路已經(jīng)介紹得非常清楚了，因此在這我們貼上代碼，大家好好體會(huì)：

let reverseList = (head) =>{   let reverse = (pre, cur) => {     if(!cur) return pre;     // 保存 next 節(jié)點(diǎn)     let next = cur.next;     cur.next = pre;     return reverse(cur, next);   }   return reverse(null, head); }

No.2 區(qū)間反轉(zhuǎn)

反轉(zhuǎn)從位置 m 到 n 的鏈表。請(qǐng)使用一趟掃描完成反轉(zhuǎn)。

說(shuō)明:1 ≤ m ≤ n ≤ 鏈表長(zhǎng)度。

示例:

輸入: 1->2->3->4->5->NULL, m = 2, n = 4 輸出: 1->4->3->2->5->NULL

來(lái)源: LeetCode 第 92 題

思路

這一題相比上一個(gè)整個(gè)鏈表反轉(zhuǎn)的題，其實(shí)是換湯不換藥。我們依然有兩種類型的解法：循環(huán)解法和遞歸解法。

需要注意的問(wèn)題就是前后節(jié)點(diǎn)的保存(或者記錄)，什么意思呢?看這張圖你就明白了。

關(guān)于前節(jié)點(diǎn)和后節(jié)點(diǎn)的定義，大家在圖上應(yīng)該能看的比較清楚了，后面會(huì)經(jīng)常用到。

反轉(zhuǎn)操作上一題已經(jīng)拆解過(guò)，這里不再贅述。值得注意的是反轉(zhuǎn)后的工作，那么對(duì)于整個(gè)區(qū)間反轉(zhuǎn)后的工作，其實(shí)就是一個(gè)移花接木的過(guò)程，首先將前節(jié)點(diǎn)的 next  指向區(qū)間終點(diǎn)，然后將區(qū)間起點(diǎn)的 next 指向后節(jié)點(diǎn)。因此這一題中有四個(gè)需要重視的節(jié)點(diǎn):  前節(jié)點(diǎn)、后節(jié)點(diǎn)、區(qū)間起點(diǎn)和區(qū)間終點(diǎn)。接下來(lái)我們開(kāi)始實(shí)際的編碼操作。

循環(huán)解法

/**  * @param {ListNode} head  * @param {number} m  * @param {number} n  * @return {ListNode}  */ var reverseBetween = function(head, m, n) {     let count = n - m;     let p = dummyHead = new ListNode();     let pre, cur, start, tail;     p.next = head;     for(let i = 0; i < m - 1; i ++) {         p = p.next;     }     // 保存前節(jié)點(diǎn)     front = p;     // 同時(shí)保存區(qū)間首節(jié)點(diǎn)     pre = tail = p.next;     cur = pre.next;     // 區(qū)間反轉(zhuǎn)     for(let i = 0; i < count; i++) {         let next = cur.next;         cur.next = pre;         pre = cur;         cur = next;     }     // 前節(jié)點(diǎn)的 next 指向區(qū)間末尾     front.next = pre;     // 區(qū)間首節(jié)點(diǎn)的 next 指向后節(jié)點(diǎn)(循環(huán)完后的cur就是區(qū)間后面第一個(gè)節(jié)點(diǎn)，即后節(jié)點(diǎn))     tail.next = cur;     return dummyHead.next; };

遞歸解法

對(duì)于遞歸解法，唯一的不同就在于對(duì)于區(qū)間的處理，采用遞歸程序進(jìn)行處理，大家也可以趁著復(fù)習(xí)一下遞歸反轉(zhuǎn)的實(shí)現(xiàn)。

var reverseBetween = function(head, m, n) {   // 遞歸反轉(zhuǎn)函數(shù)   let reverse = (pre, cur) => {     if(!cur) return pre;     // 保存 next 節(jié)點(diǎn)     let next = cur.next;     cur.next = pre;     return reverse(cur, next);   }   let p = dummyHead = new ListNode();   dummyHead.next = head;   let start, end; //區(qū)間首尾節(jié)點(diǎn)   let front, tail; //前節(jié)點(diǎn)和后節(jié)點(diǎn)   for(let i = 0; i < m - 1; i++) {     p = p.next;   }   front = p; //保存前節(jié)點(diǎn)   start = front.next;   for(let i = m - 1; i < n; i++) {     p = p.next;   }   end = p;   tail = end.next; //保存后節(jié)點(diǎn)   end.next = null;   // 開(kāi)始穿針引線啦，前節(jié)點(diǎn)指向區(qū)間首，區(qū)間首指向后節(jié)點(diǎn)   front.next = reverse(null, start);   start.next = tail;   return dummyHead.next; }

No.3 兩個(gè)一組翻轉(zhuǎn)鏈表

給定一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后的鏈表。

你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

來(lái)源: LeetCode 第 24 題

示例:

給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.

思路

如圖所示，我們首先建立一個(gè)虛擬頭節(jié)點(diǎn)(dummyHead)，輔助我們分析。

首先讓 p 處在 dummyHead 的位置，記錄下 p.next 和 p.next.next 的節(jié)點(diǎn)，也就是 node1 和 node2。

隨后讓 node1.next = node2.next, 效果:

然后讓 node2.next = node1, 效果:

最后，dummyHead.next = node2，本次翻轉(zhuǎn)完成。同時(shí) p 指針指向node1, 效果如下：

依此循環(huán)，如果 p.next 或者 p.next.next 為空，也就是找不到新的一組節(jié)點(diǎn)了，循環(huán)結(jié)束。

循環(huán)解決

思路清楚了，其實(shí)實(shí)現(xiàn)還是比較容易的，代碼如下:

var swapPairs = function(head) {     if(head == null || head.next == null)          return head;     let dummyHead = p = new ListNode();     let node1, node2;     dummyHead.next = head;     while((node1 = p.next) && (node2 = p.next.next)) {         node1.next = node2.next;         node2.next = node1;         p.next = node2;         p = node1;     }     return dummyHead.next; };

遞歸方式

var swapPairs = function(head) {     if(head == null || head.next == null)         return head;     let node1 = head, node2 = head.next;     node1.next = swapPairs(node2.next);     node2.next = node1;     return node2; };

利用遞歸方式之后，是不是感覺(jué)代碼特別簡(jiǎn)潔????

希望你能好好體會(huì)一下遞歸調(diào)用的過(guò)程，相信理解之后對(duì)自己是一個(gè)很大的提升。

No.4 K個(gè)一組翻轉(zhuǎn)鏈表

給你一個(gè)鏈表，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)，請(qǐng)你返回翻轉(zhuǎn)后的鏈表。

k 是一個(gè)正整數(shù)，它的值小于或等于鏈表的長(zhǎng)度。

如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么請(qǐng)將最后剩余的節(jié)點(diǎn)保持原有順序。

示例 :

給定這個(gè)鏈表：1->2->3->4->5 當(dāng) k = 2 時(shí)，應(yīng)當(dāng)返回: 2->1->4->3->5 當(dāng) k = 3 時(shí)，應(yīng)當(dāng)返回: 3->2->1->4->5

說(shuō)明 :

• 你的算法只能使用常數(shù)的額外空間。

• 你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

來(lái)源: LeetCode 第 25 題

思路

思路類似No.3中的兩個(gè)一組翻轉(zhuǎn)。唯一的不同在于兩個(gè)一組的情況下每一組只需要反轉(zhuǎn)兩個(gè)節(jié)點(diǎn)，而在 K 個(gè)一組的情況下對(duì)應(yīng)的操作是將 K  個(gè)元素的鏈表進(jìn)行反轉(zhuǎn)。

遞歸解法

這一題我覺(jué)得遞歸的解法更容易理解，因此，先貼上遞歸方法的代碼。

• 以下代碼的注釋中`首節(jié)點(diǎn)`、`尾結(jié)點(diǎn)`等概念都是針對(duì)反轉(zhuǎn)前的鏈表而言的。

/**  * @param {ListNode} head  * @param {number} k  * @return {ListNode}  */ var reverseKGroup = function(head, k) {     let pre = null, cur = head;     let p = head;     // 下面的循環(huán)用來(lái)檢查后面的元素是否能組成一組     for(let i = 0; i < k; i++) {         if(p == null) return head;         p = p.next;     }     for(let i = 0; i < k; i++){         let next = cur.next;         cur.next = pre;         pre = cur;         cur = next;     }     // pre為本組最后一個(gè)節(jié)點(diǎn)，cur為下一組的起點(diǎn)     head.next = reverseKGroup(cur, k);     return pre; };

循環(huán)解法

重點(diǎn)都放在注釋里面了。

var reverseKGroup = function(head, k) {     let count = 0;     // 看是否能構(gòu)成一組，同時(shí)統(tǒng)計(jì)鏈表元素個(gè)數(shù)     for(let p = head; p != null; p = p.next) {         if(p == null && i < k) return head;         count++;     }     let loopCount = Math.floor(count / k);     let p = dummyHead = new ListNode();     dummyHead.next = head;     // 分成了 loopCount 組，對(duì)每一個(gè)組進(jìn)行反轉(zhuǎn)     for(let i = 0; i < loopCount; i++) {         let pre = null, cur = p.next;         for(let j = 0; j < k; j++) {             let next = cur.next;             cur.next = pre;             pre = cur;             cur = next;         }         // 當(dāng)前 pre 為該組的尾結(jié)點(diǎn)，cur 為下一組首節(jié)點(diǎn)         let start = p.next;// start 是該組首節(jié)點(diǎn)         // 開(kāi)始穿針引線！思路和2個(gè)一組的情況一模一樣         p.next = pre;         start.next = cur;         p = start;     }     return dummyHead.next; };

環(huán)形鏈表

NO.1 如何檢測(cè)鏈表形成環(huán)?

給定一個(gè)鏈表，判斷鏈表中是否形成環(huán)。

思路

思路一: 循環(huán)一遍，用 Set 數(shù)據(jù)結(jié)構(gòu)保存節(jié)點(diǎn)，利用節(jié)點(diǎn)的內(nèi)存地址來(lái)進(jìn)行判重，如果同樣的節(jié)點(diǎn)走過(guò)兩次，則表明已經(jīng)形成了環(huán)。

思路二: 利用快慢指針，快指針一次走兩步，慢指針一次走一步，如果兩者相遇，則表明已經(jīng)形成了環(huán)。

可能你會(huì)納悶，為什么思路二用兩個(gè)指針在環(huán)中一定會(huì)相遇呢?

其實(shí)很簡(jiǎn)單，如果有環(huán)，兩者一定同時(shí)走到環(huán)中，那么在環(huán)中，選慢指針為參考系，快指針每次相對(duì)參考系向前走一步，終究會(huì)繞回原點(diǎn)，也就是回到慢指針的位置，從而讓兩者相遇。如果沒(méi)有環(huán)，則兩者的相對(duì)距離越來(lái)越遠(yuǎn)，永遠(yuǎn)不會(huì)相遇。

接下來(lái)我們來(lái)編程實(shí)現(xiàn)。

方法一: Set 判重

/**  * @param {ListNode} head  * @return {boolean}  */ var hasCycle = (head) => {     let set = new Set();     let p = head;     while(p) {         // 同一個(gè)節(jié)點(diǎn)再次碰到，表示有環(huán)         if(set.has(p)) return true;         set.add(p);         p = p.next;     }     return false; }

方法二: 快慢指針

var hasCycle = function(head) {     let dummyHead = new ListNode();     dummyHead.next = head;     let fast = slow = dummyHead;     // 零個(gè)結(jié)點(diǎn)或者一個(gè)結(jié)點(diǎn)，肯定無(wú)環(huán)     if(fast.next == null || fast.next.next == null)          return false;     while(fast && fast.next) {         fast = fast.next.next;         slow = slow.next;         // 兩者相遇了         if(fast == slow) {             return true;         }     }      return false; };

No.2 如何找到環(huán)的起點(diǎn)

給定一個(gè)鏈表，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)。 如果鏈表無(wú)環(huán)，則返回 null。

**說(shuō)明：**不允許修改給定的鏈表。

思路分析

剛剛已經(jīng)判斷了如何判斷出現(xiàn)環(huán)，那如何找到環(huán)的節(jié)點(diǎn)呢?我們來(lái)分析一波。

看上去比較繁瑣，我們把它做進(jìn)一步的抽象:

設(shè)快慢指針走了x秒，慢指針一秒走一次。

對(duì)快指針，有: 2x - L = m * S + Y -----①

對(duì)慢指針，有: x - L = n * S + Y -----②

其中，m、n 均為自然數(shù)。

① - ② * 2 得:

L = (m - n) * S - Y-----③

好，這是一個(gè)非常重要的等式。我們現(xiàn)在假設(shè)有一個(gè)新的指針在 L 段的最左端，慢指針現(xiàn)在還在相遇處。

讓新指針和慢指針都每次走一步，那么，當(dāng)新指針走了 L 步之后到達(dá)環(huán)起點(diǎn)，而與此同時(shí)，我們看看慢指針情況如何。

由③式，慢指針走了(m - n) * S - Y個(gè)單位，以環(huán)起點(diǎn)為參照物，相遇時(shí)的位置為 Y，而現(xiàn)在由Y + (m - n) * S - Y即(m -  n) * S，得知慢指針實(shí)際上參照環(huán)起點(diǎn)，走了整整(m - n)圈。也就是說(shuō)，慢指針此時(shí)也到達(dá)了環(huán)起點(diǎn)。:::tip 結(jié)論  現(xiàn)在的解法就很清晰了，當(dāng)快慢指針相遇之后，讓新指針從頭出發(fā)，和慢指針同時(shí)前進(jìn)，且每次前進(jìn)一步，兩者相遇的地方，就是環(huán)起點(diǎn)。:::

編程實(shí)現(xiàn)

懂得原理之后，實(shí)現(xiàn)起來(lái)就容易很多了。

/**  * @param {ListNode} head  * @return {ListNode}  */ var detectCycle = function(head) {     let dummyHead = new ListNode();     dummyHead.next = head;     let fast = slow = dummyHead;     // 零個(gè)結(jié)點(diǎn)或者一個(gè)結(jié)點(diǎn)，肯定無(wú)環(huán)     if(fast.next == null || fast.next.next == null)          return null;     while(fast && fast.next) {         fast = fast.next.next;         slow = slow.next;         // 兩者相遇了         if(fast == slow) {            let p = dummyHead;            while(p != slow) {                p = p.next;                slow = slow.next;            }            return p;         }     }      return null; };

鏈表合并

NO.1 合并兩個(gè)有序鏈表

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例:

輸入：1->2->4, 1->3->4 輸出：1->1->2->3->4->4

來(lái)源: LeetCode第21題

遞歸解法

遞歸解法更容易理解，我們先用遞歸來(lái)做一下:

/**  * @param {ListNode} l1  * @param {ListNode} l2  * @return {ListNode}  */ var mergeTwoLists = function(l1, l2) {     const merge = (l1, l2) => {         if(l1 == null) return l2;         if(l2 == null) return l1;         if(l1.val > l2.val) {             l2.next = merge(l1, l2.next);             return l2;         }else {             l1.next = merge(l1.next, l2);             return l1;         }     }     return merge(l1, l2); };

循環(huán)解法

var mergeTwoLists = function(l1, l2) {     if(l1 == null) return l2;     if(l2 == null) return l1;     let p = dummyHead = new ListNode();     let p1 = l1, p2 = l2;     while(p1 && p2) {         if(p1.val > p2.val) {             p.next = p2;             p = p.next;             p2 = p2.next;         }else {             p.next = p1;             p = p.next;             p1 = p1.next;         }     }     // 循環(huán)完成后務(wù)必檢查剩下的部分     if(p1) p.next = p1;     else p.next = p2;     return dummyHead.next; };

No.2 合并 K 個(gè)有序鏈表

合并 k 個(gè)排序鏈表，返回合并后的排序鏈表。請(qǐng)分析和描述算法的復(fù)雜度。

示例:

輸入: [   1->4->5,   1->3->4,   2->6 ] 輸出: 1->1->2->3->4->4->5->6

來(lái)源: LeetCode第23題

自上而下(遞歸)實(shí)現(xiàn)

/**  * @param {ListNode[]} lists  * @return {ListNode}  */ var mergeKLists = function(lists) {     // 上面已經(jīng)實(shí)現(xiàn)     var mergeTwoLists = function(l1, l2) {/*上面已經(jīng)實(shí)現(xiàn)*/};     const _mergeLists = (lists, start, end) => {         if(end - start < 0) return null;         if(end - start == 0)return lists[end];         let mid = Math.floor(start + (end - start) / 2);         return mergeTwoList(_mergeLists(lists, start, mid), _mergeLists(lists, mid + 1, end));     }     return _mergeLists(lists, 0, lists.length - 1); };

自下而上實(shí)現(xiàn)

在這里需要提醒大家的是，在自下而上的實(shí)現(xiàn)方式中，我為每一個(gè)鏈表綁定了一個(gè)虛擬頭指針(dummyHead)，為什么這么做?

這是為了方便鏈表的合并，比如 l1 和 l2 合并之后，合并后鏈表的頭指針就直接是 l1 的 dummyHead.next 值，等于說(shuō)兩個(gè)鏈表都合并到了  l1 當(dāng)中，方便了后續(xù)的合并操作。

var mergeKLists = function(lists) {     var mergeTwoLists = function(l1, l2) {/*上面已經(jīng)實(shí)現(xiàn)*/};     // 邊界情況     if(!lists || !lists.length) return null;     // 虛擬頭指針集合     let dummyHeads = [];     // 初始化虛擬頭指針     for(let i = 0; i < lists.length; i++) {         let node = new ListNode();         node.next = lists[i];         dummyHeads[i] = node;     }     // 自底向上進(jìn)行merge     for(let size = 1; size < lists.length; size += size){         for(let i = 0; i + size < lists.length;i += 2 * size) {             dummyHeads[i].next = mergeTwoLists(dummyHeads[i].next, dummyHeads[i + size].next);         }     }     return dummyHeads[0].next; };

多個(gè)鏈表的合并到這里就實(shí)現(xiàn)完成了，在這里順便告訴你這種歸并的方式同時(shí)也是對(duì)鏈表進(jìn)行歸并排序的核心代碼。希望你能好好體會(huì)自上而下和自下而上兩種不同的實(shí)現(xiàn)細(xì)節(jié)，相信對(duì)你的編程內(nèi)功是一個(gè)不錯(cuò)的提升。

求鏈表中間節(jié)點(diǎn)

判斷回文鏈表

請(qǐng)判斷一個(gè)單鏈表是否為回文鏈表。

示例1:

輸入: 1->2 輸出: false

示例2:

輸入: 1->2->2->1 輸出: true

你能否用 O(n) 時(shí)間復(fù)雜度和 O(1) 空間復(fù)雜度解決此題?

來(lái)源: LeetCode第234題

思路分析

這一題如果不考慮性能的限制，其實(shí)是非常簡(jiǎn)單的。但考慮到 O(n) 時(shí)間復(fù)雜度和 O(1) 空間復(fù)雜度，恐怕就值得停下來(lái)好好想想了。

題目的要求是單鏈表，沒(méi)有辦法訪問(wèn)前面的節(jié)點(diǎn)，那我們只得另辟蹊徑:

找到鏈表中點(diǎn)，然后將后半部分反轉(zhuǎn)，就可以依次比較得出結(jié)論了。下面我們來(lái)實(shí)現(xiàn)一波。

代碼實(shí)現(xiàn)

其實(shí)關(guān)鍵部分的代碼就是找中點(diǎn)了。先亮劍:

let dummyHead = slow = fast = new ListNode(); dummyHead.next = head; // 注意注意，來(lái)找中點(diǎn)了 while(fast && fast.next) {     slow = slow.next;     fast = fast.next.next; }

你可能會(huì)納悶了，為什么邊界要設(shè)成這樣?

我們不妨來(lái)分析一下，分鏈表節(jié)點(diǎn)個(gè)數(shù)為奇數(shù)和偶數(shù)的時(shí)候分別討論。

當(dāng)鏈表節(jié)點(diǎn)個(gè)數(shù)為奇數(shù)

試著模擬一下， fast 為空的時(shí)候，停止循環(huán), 狀態(tài)如下:

當(dāng)鏈表節(jié)點(diǎn)個(gè)數(shù)為偶數(shù)

模擬走一遍，當(dāng) fast.next  為空的時(shí)候，停止循環(huán)，狀態(tài)如下:

對(duì)于 fast 為空和fast.next為空兩個(gè)條件，在奇數(shù)的情況下，總是 fast為空先出現(xiàn)，偶數(shù)的情況下，總是fast.next先出現(xiàn).

也就是說(shuō): 一旦fast為空, 鏈表節(jié)點(diǎn)個(gè)數(shù)一定為奇數(shù)，否則為偶數(shù)。因此兩種情況可以合并來(lái)討論，當(dāng) fast 為空或者 fast.next  為空，循環(huán)就可以終止了。

完整實(shí)現(xiàn)如下:

/**  * @param {ListNode} head  * @return {boolean}  */ var isPalindrome = function(head) {     let reverse = (pre, cur) => {         if(!cur) return pre;         let next = cur.next;         cur.next = pre;         return reverse(cur, next);     }     let dummyHead = slow = fast = new ListNode();     dummyHead.next = head;     // 注意注意，來(lái)找中點(diǎn)了, 黃金模板     while(fast && fast.next) {         slow = slow.next;         fast = fast.next.next;     }     let next = slow.next;     slow.next = null;     let newStart = reverse(null, next);     for(let p = head, newP = newStart; newP != null; p = p.next, newP = newP.next) {         if(p.val != newP.val) return false;     }     return true; };

感謝各位的閱讀，以上就是“前端算法系統(tǒng)練習(xí)之怎么掌握鏈表”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)前端算法系統(tǒng)練習(xí)之怎么掌握鏈表這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！