最近也做了很多題目容劳，但是回過頭一看發(fā)現(xiàn)好多題目雖然當時是我獨立思考出來的祟辟，但是我又忘了該怎么做了，又得花好長時間是思考。不過想來想去發(fā)現(xiàn)其實大部分題目還是有套路的洪规，所以我覺得是時候去總結(jié)一下這些套路印屁。這是個系列文章，將會總結(jié)一些常見題型的套路斩例。第一篇先說說鏈表雄人。我遇見的所有算法題目所涉及到的鏈表，都是單鏈表念赶，因此這里也只說單鏈表础钠。
單鏈表其實就是一個data加上一個next指針。由于一個節(jié)點只通過next指針保存了它的下一個節(jié)點晶乔，失去了它的前驅(qū)節(jié)點信息珍坊，因此幾乎所有單鏈表題目都是在前驅(qū)節(jié)點做文章。同時正罢，單鏈表數(shù)據(jù)結(jié)構(gòu)通常長度未知阵漏，很多題目也會在長度上做文章》撸基本上思考鏈表題目就這么兩個思路下手履怯。
圍繞這兩個問題，鏈表大致有以下幾種經(jīng)典題型：
- 雙指針
- 模擬高精度加減法
- 翻轉(zhuǎn)鏈表（全部or部分）
雙指針
針對于雙指針裆泳，實際上更細化也分兩種：
- 快慢指針
- 前后指針
比如說:
19. 刪除鏈表的倒數(shù)第N個節(jié)點叹洲，鏈表涉及到長度，馬上應(yīng)該聯(lián)想到雙指針工禾。由于長度未知运提，倒數(shù)第N個怎么找？兩個指針闻葵，第一個先走N步民泵，第二個原地不動。然后一起遍歷槽畔，當前面指針到最后時栈妆，后面的指針就指向倒數(shù)第N
61. 旋轉(zhuǎn)鏈表，旋轉(zhuǎn)k相當于把尾節(jié)點連到頭結(jié)點厢钧，然后在倒數(shù)第k個節(jié)點處斷開鳞尔。但是這里需要遍歷一次鏈表取得總長度n，因為k很可能非常大早直，需要對n取模寥假。也是一個經(jīng)典的前后指針的運用
環(huán)形鏈表，判斷鏈表是否有環(huán)霞扬。鏈表有環(huán)說明next永遠不為None糕韧，此時采用快慢指針拾给，一個指針快（一次走2步）一個指針慢（一次走1步），如果有環(huán)兔沃，快指針某個時刻就會追上滿指針（跑步超圈）。如果快指針走到None節(jié)點级及，說明無環(huán)乒疏。
針對鏈表的環(huán)，其實也有兩個經(jīng)典題目饮焦，一個是求環(huán)的起點142. 環(huán)形鏈表 II
怕吴，一個是求環(huán)的長度。
求環(huán)的長度其實可以轉(zhuǎn)化成小學(xué)數(shù)學(xué)的追及問題县踢。當快慢指針第一次相遇時转绷，此時節(jié)點肯定在環(huán)上某個位置。我們以此為起點繼續(xù)走硼啤，同時記錄步數(shù)t议经。當快慢指針再次相遇時，相當于速度為2的經(jīng)過t秒比速度為1的多跑了一圈谴返，2*t-1*t=t煞肾，因此環(huán)的長度就是t
而求環(huán)的起點則稍微需要畫個圖來理解。（暫時缺圖嗓袱，后面補籍救，證明過程在圖上）總之結(jié)論就是，當快慢指針第一次相遇后渠抹，慢指針到環(huán)的起點的距離和鏈表頭指針到環(huán)起點距離相等蝙昙。也就是說，此時利用一個新的指針梧却，從頭開始走奇颠，當和慢指針相遇時，該節(jié)點就是環(huán)的起點篮幢。
環(huán)形鏈表的一個變種就是求兩個鏈表的交點大刊，比如160. 相交鏈表。這道題表面上看起來有兩個鏈表三椿，不過如果做一個輔助線缺菌，比如把B鏈表首尾相連，也就是讓鏈表的末節(jié)點指向B鏈表的表頭搜锰，那么這道題就變成了求單鏈表的環(huán)的起點伴郁。當然這種思路就需要做題時積累了，臨場想的話還是稍微有點費勁蛋叼。
翻轉(zhuǎn)鏈表
翻轉(zhuǎn)鏈表就是很直接的題目焊傅，主要是考實現(xiàn)而不是考算法剂陡。翻轉(zhuǎn)鏈表的題目就比較種類繁多了，但各種翻轉(zhuǎn)都萬變不離其宗狐胎。只要掌握了翻轉(zhuǎn)整個鏈表的方法鸭栖，剩下大部分的都是花式處理邊界case。
fn reverse_list(mut head: Option<Box<ListNode>>) ->
Option<Box<ListNode>> {
let mut new_head = None;
while let Some(node) = head.take() {
let new_node = ListNode{
val: node.val,
next: new_head.take(),
};
new_head = new_node;
head = node.next;
}
new_head
}
以上是通過新建鏈表來進行翻轉(zhuǎn)握巢，實際上還可以原地翻轉(zhuǎn)晕鹊，Rust不太方便實現(xiàn)，Go的偽代碼如下：
func reverseLinkedList(head *ListNode) *ListNode {
if head == nil {
return nil
}
var newHead *ListNode
cur := head
for cur != nil {
next := cur.Next
cur.Next = newHead
newHead = cur
cur = next
}
return newHead
}
這種原地翻轉(zhuǎn)實際上只是改變了節(jié)點指針的指向暴浦，更簡單了溅话。
由于直接翻轉(zhuǎn)鏈表很簡單，因此大部分題目都是花式翻轉(zhuǎn)歌焦，比如：
25. K 個一組翻轉(zhuǎn)鏈表和24. 兩兩交換鏈表中的節(jié)點（相當于K=2）,當我們在翻轉(zhuǎn)鏈表中的連續(xù)k個節(jié)點時飞几，實際上和翻轉(zhuǎn)整個鏈表沒有區(qū)別。但是需要注意的是独撇，翻轉(zhuǎn)完的鏈表需要接到之前的鏈表后面屑墨，即
pre.Next = newHead，同時纷铣，因為要繼續(xù)翻轉(zhuǎn)接下來的k個绪钥，因此還要記錄翻轉(zhuǎn)后鏈表的尾節(jié)點。當發(fā)現(xiàn)最后一次不足k個時关炼，還要把已經(jīng)翻轉(zhuǎn)的鏈表再翻轉(zhuǎn)回去程腹。234. 回文鏈表，判斷一個鏈表是否是回文的儒拂，利用快慢指針找到中點寸潦，然后把后半部分翻轉(zhuǎn)。如果是回文的社痛，翻轉(zhuǎn)之后后半部分和前半部分應(yīng)該是一樣的
143. 重排鏈表见转，要把
L0->L1->L2->L3->L4變成L0->L4->L1->L3->L2，其實相當于把鏈表前一半不動L0->L1->L2蒜哀，后一半翻轉(zhuǎn)L4->L3斩箫，然后把翻轉(zhuǎn)后的節(jié)點插入到前一半鏈表的縫隙中L0-> (L4) -> L1-> (L3) -> L2。關(guān)鍵詞一半撵儿、翻轉(zhuǎn)乘客。因此，利用快慢指針找到前一半淀歇，然后把后一半翻轉(zhuǎn)偷霉，最后再插空洋措。
翻轉(zhuǎn)鏈表變種題目盆均，大多數(shù)可能需要開辟額外空間或者建立新的虛擬鏈表，最終再拼接回去缀匕。比如：
- 86. 分隔鏈表，給鏈表重新排序碰逸，小于x的元素要在大于等于x的元素的前面乡小，剩下的元素相對順序不變。這道題就可以建立兩個虛擬鏈表饵史，小于x的放到before鏈表中劲件，大于等于的放到after鏈表，最終再把after放到before后面约急。
- 328. 奇偶鏈表，同樣建立兩個虛擬鏈表苗分，一個保存奇數(shù)個節(jié)點一個保存偶數(shù)個厌蔽，最后合并回去
- 725. 分隔鏈表，先求出鏈表總長度n摔癣，然后計算每個部分要放幾個元素奴饮，前n%k個部分要多一個元素，直接遍歷即可择浊。
高精度運算
這類題不多戴卜，但是其實解法很簡單。因為加減法涉及到進位琢岩，所以先翻轉(zhuǎn)鏈表投剥，然后進行加法操作即可。
總結(jié)
經(jīng)過上面的總結(jié)担孔，其實鏈表基本就這么些題型江锨，只要掌握了這些題型和核心解題思路，拿起雙指針和翻轉(zhuǎn)兩大武器糕篇，基本上就不怕鏈表的題目了啄育。
