前端算法系統(tǒng)練習(xí): 鏈表篇完結(jié)

反轉(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)做鏈表開篇的訓(xùn)練類型，希望大家能引起足夠的重視?。

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

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

示例:

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

來源: LeetCode 第 206 題

循環(huán)解決方案

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

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

保存后續(xù)節(jié)點(diǎn)。作為新手來說，很容易將當(dāng)前節(jié)點(diǎn)的 next指針直接指向前一個(gè)節(jié)點(diǎn)，但其實(shí)當(dāng)前節(jié)點(diǎn)下一個(gè)節(jié)點(diǎn)的指針也就丟失了。因此，需要在遍歷的過程當(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;
};

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

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

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

但作為系統(tǒng)性的訓(xùn)練而言，單單讓程序通過未免太草率了，我們后續(xù)會(huì)盡可能地用不同的方式去解決相同的問題，達(dá)到融會(huì)貫通的效果，也是對自己思路的開拓，有時(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 的鏈表。請使用一趟掃描完成反轉(zhuǎn)。

說明:1 ≤ m ≤ n ≤ 鏈表長度。

示例:

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

來源: LeetCode 第 92 題

思路

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

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

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

反轉(zhuǎn)操作上一題已經(jīng)拆解過，這里不再贅述。值得注意的是反轉(zhuǎn)后的工作，那么對于整個(gè)區(qū)間反轉(zhuǎn)后的工作，其實(shí)就是一個(gè)移花接木的過程，首先將前節(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)。接下來我們開始實(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?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?????????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;
};

遞歸解法

對于遞歸解法，唯一的不同就在于對于區(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?1;?i++)?{
????p?=?p.next;
??}
??front?=?p;?//保存前節(jié)點(diǎn)
??start?=?front.next;
??for(let?i?=?m?-?1;?i?????p?=?p.next;
??}
??end?=?p;
??tail?=?end.next;?//保存后節(jié)點(diǎn)
??end.next?=?null;
??//?開始穿針引線啦，前節(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)交換。

來源: 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;
};

利用遞歸方式之后，是不是感覺代碼特別簡潔？???

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

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

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

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

如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么請將最后剩余的節(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

說明 :

• 你的算法只能使用常數(shù)的額外空間。
• 你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

來源: LeetCode 第 25 題

思路

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

遞歸解法

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

以下代碼的注釋中`首節(jié)點(diǎn)`、`尾結(jié)點(diǎn)`等概念都是針對反轉(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)用來檢查后面的元素是否能組成一組
????for(let?i?=?0;?i?????????if(p?==?null)?return?head;
????????p?=?p.next;
????}
????for(let?i?=?0;?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?return?head;
????????count++;
????}
????let?loopCount?=?Math.floor(count?/?k);
????let?p?=?dummyHead?=?new?ListNode();
????dummyHead.next?=?head;
????//?分成了?loopCount?組，對每一個(gè)組進(jìn)行反轉(zhuǎn)
????for(let?i?=?0;?i?????????let?pre?=?null,?cur?=?p.next;
????????for(let?j?=?0;?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)
????????//?開始穿針引線！思路和2個(gè)一組的情況一模一樣
????????p.next?=?pre;
????????start.next?=?cur;
????????p?=?start;
????}
????return?dummyHead.next;
};

環(huán)形鏈表

No.1 如何檢測鏈表形成環(huán)？

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

思路

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

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

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

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

接下來我們來編程實(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)，肯定無環(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è)鏈表，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。?如果鏈表無環(huán)，則返回 null。

**說明：**不允許修改給定的鏈表。

思路分析

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

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

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

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

對慢指針，有: 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)圈。也就是說，慢指針此時(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)起來就容易很多了。

/**
?*?@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)，肯定無環(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è)新的有序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例:

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

來源: LeetCode第21題

遞歸解法

遞歸解法更容易理解，我們先用遞歸來做一下:

/**
?*?@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è)排序鏈表，返回合并后的排序鏈表。請分析和描述算法的復(fù)雜度。

示例:

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

來源: 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 值，等于說兩個(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?????????let?node?=?new?ListNode();
????????node.next?=?lists[i];
????????dummyHeads[i]?=?node;
????}
????//?自底向上進(jìn)行merge
????for(let?size?=?1;?size?????????for(let?i?=?0;?i?+?size?2?*?size)?{
????????????dummyHeads[i].next?=?mergeTwoLists(dummyHeads[i].next,?dummyHeads[i?+?size].next);
????????}
????}
????return?dummyHeads[0].next;
};

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

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

判斷回文鏈表

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

示例1:

輸入:?1->2
輸出:?false

示例2:

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

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

來源: LeetCode第234題

思路分析

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

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

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

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

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

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

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

我們不妨來分析一下，分鏈表節(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)如下:

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

也就是說: 一旦fast為空, 鏈表節(jié)點(diǎn)個(gè)數(shù)一定為奇數(shù)，否則為偶數(shù)。因此兩種情況可以合并來討論，當(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;
????//?注意注意，來找中點(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;
};