203. removeElements 函數(shù)

這個(gè)函數(shù)用于從鏈表中移除所有值為 val 的節(jié)點(diǎn)。

• 使用了一個(gè)啞節(jié)點(diǎn)（dummy node）來簡化頭節(jié)點(diǎn)的處理最爬。
• 初始化一個(gè) current 指針涉馁，從啞節(jié)點(diǎn)開始遍歷。
• 當(dāng) current.next 的值等于給定的 val 時(shí)爱致，通過 current.next = current.next.next; 來跳過并刪除該節(jié)點(diǎn)烤送。
• 否則，繼續(xù)向下遍歷糠悯。

返回時(shí)剔除啞節(jié)點(diǎn)胯努，返回 dummy.next。

141. hasCycle 函數(shù)

這個(gè)函數(shù)用于判斷一個(gè)鏈表是否包含環(huán)逢防。

• 使用兩個(gè)指針：slow 和 fast叶沛。
• slow 每次向前移動一個(gè)節(jié)點(diǎn)，而 fast 每次向前移動兩個(gè)節(jié)點(diǎn)忘朝。
• 如果鏈表中有環(huán)灰署，那么 slow 和 fast 指針最終會相遇。
• 如果 fast 到達(dá)鏈表末尾，說明鏈表沒有環(huán)溉箕。

這兩個(gè)函數(shù)分別解決了鏈表中的元素刪除和環(huán)檢測問題晦墙，使用了不同的遍歷和指針操作技巧。希望這個(gè)總結(jié)能幫助你更好地理解這兩個(gè)函數(shù)肴茄！

206 翻轉(zhuǎn)鏈表

整個(gè)翻轉(zhuǎn)過程依賴于三個(gè)指針：prev晌畅、current 和 next。

1. prev 用于跟蹤當(dāng)前節(jié)點(diǎn)（current）的前一個(gè)節(jié)點(diǎn)寡痰。
2. current 用于跟蹤當(dāng)前需要翻轉(zhuǎn)的節(jié)點(diǎn)抗楔。
3. next 用于臨時(shí)存儲 current 的下一個(gè)節(jié)點(diǎn)，因?yàn)樵诜D(zhuǎn)過程中 current.next 會被改變拦坠。

算法的核心步驟如下：

1. next = current.next 臨時(shí) 连躏。存儲當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)到 next。
2. current.next = prev 翻轉(zhuǎn)贞滨。改變當(dāng)前節(jié)點(diǎn) current 的 next 指針入热，使其指向 prev，從而實(shí)現(xiàn)局部翻轉(zhuǎn)晓铆。
3. prev = current 跟隨勺良。將 prev 更新為當(dāng)前節(jié)點(diǎn) current。跟隨 current
4. current = next 移動骄噪。將 current 更新為 next尚困，即向鏈表的末尾方向移動。

通過循環(huán)執(zhí)行這些步驟腰池，鏈表最終會完全翻轉(zhuǎn)尾组。

這個(gè)算法不僅直觀，而且實(shí)現(xiàn)簡單示弓，時(shí)間復(fù)雜度是O(n)讳侨，其中 n 是鏈表的長度。希望這個(gè)總結(jié)能幫助你更好地理解這個(gè)問題奏属！

21 合并兩個(gè)有序鏈表

1. 初始化啞節(jié)點(diǎn)和當(dāng)前指針：創(chuàng)建一個(gè)啞節(jié)點(diǎn)作為合并后鏈表的“虛擬”頭節(jié)點(diǎn)跨跨，并使用一個(gè)當(dāng)前指針（cur）來追蹤新鏈表的最后一個(gè)節(jié)點(diǎn)。
2. 遍歷兩個(gè)鏈表：當(dāng)兩個(gè)輸入鏈表 list1 和 list2 都不為空時(shí)囱皿，比較它們當(dāng)前節(jié)點(diǎn)的值勇婴。
3. 節(jié)點(diǎn)添加與指針移動：
   • 如果 list1 當(dāng)前節(jié)點(diǎn)的值大于 list2，則將 list2 當(dāng)前節(jié)點(diǎn)添加到新鏈表的末尾嘱腥，并將 list2 的指針向下移動耕渴。
   • 否則，將 list1 當(dāng)前節(jié)點(diǎn)添加到新鏈表的末尾齿兔，并將 list1 的指針向下移動橱脸。
   • 在每次添加節(jié)點(diǎn)后础米，將 cur 指針移動到新鏈表的末尾。
4. 處理剩余節(jié)點(diǎn)：如果其中一個(gè)鏈表提前遍歷完成添诉，將另一個(gè)鏈表的剩余部分添加到新鏈表的末尾屁桑。
5. 返回結(jié)果：返回 dummy.next，因?yàn)?dummy 是啞節(jié)點(diǎn)栏赴，而 dummy.next 指向合并后的鏈表的實(shí)際頭節(jié)點(diǎn)蘑斧。

通過這種方式，你可以創(chuàng)建一個(gè)新的有序鏈表须眷，它包含了兩個(gè)輸入鏈表的所有節(jié)點(diǎn)竖瘾，同時(shí)也保持了排序。

876. 鏈表的中間結(jié)點(diǎn)

1. 初始化兩個(gè)指針：slow 和 fast 都初始化為鏈表的頭節(jié)點(diǎn) head柒爸。
2. 開始遍歷：只要 fast 指針和 fast.next 不為 null准浴，繼續(xù)遍歷事扭。
3. 移動指針：
   • slow 指針每次向前移動一個(gè)節(jié)點(diǎn)捎稚。
   • fast 指針每次向前移動兩個(gè)節(jié)點(diǎn)。
4. 找到中間節(jié)點(diǎn)：當(dāng) fast 指針到達(dá)鏈表末尾或者無法再向前移動時(shí)求橄，slow 指針就會指向鏈表的中間節(jié)點(diǎn)今野。
5. 返回結(jié)果：返回 slow 指針?biāo)赶虻墓?jié)點(diǎn)，即鏈表的中間節(jié)點(diǎn)罐农。

該算法使用快慢指針的方法条霜，fast 指針移動的速度是 slow 指針的兩倍。因此涵亏，當(dāng) fast 到達(dá)鏈表的末尾時(shí)宰睡，slow 會位于鏈表的中間。

整體而言气筋，這是一個(gè)非常有效的方法拆内，時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)宠默。希望這個(gè)總結(jié)能幫助你理解你自己寫的代碼麸恍！

19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

1. 初始化：創(chuàng)建一個(gè)啞節(jié)點(diǎn)并將其 next 指針指向鏈表的頭節(jié)點(diǎn)。設(shè)置兩個(gè)指針搀矫，fast 和 slow抹沪，并讓它們都指向啞節(jié)點(diǎn)。
2. 移動 fast 指針：讓 fast 指針先向前移動 n+1 步瓤球。
3. 同時(shí)移動 fast 和 slow：接下來融欧，同時(shí)移動 fast 和 slow 指針，直到 fast 指針達(dá)到鏈表的末尾（null）卦羡。
4. 刪除節(jié)點(diǎn)：此時(shí)噪馏，slow 指針將位于要刪除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)权她。通過改變 slow.next 的指向來刪除該節(jié)點(diǎn)。
5. 返回結(jié)果：最后逝薪，返回啞節(jié)點(diǎn)的 next 指針隅要，因?yàn)閱」?jié)點(diǎn)是我們?yōu)榱朔奖悴僮鞫R時(shí)添加的。
   這樣董济，我們就能在一趟遍歷中刪除鏈表中倒數(shù)第 n 個(gè)節(jié)點(diǎn)步清。希望這個(gè)總結(jié)能幫助你理解這道題！

234. 回文鏈表

這道題目要求判斷一個(gè)單鏈表是否為回文結(jié)構(gòu)虏肾。解題的主要步驟如下：

• 尋找中間節(jié)點(diǎn)：使用兩個(gè)指針（fast 和 slow）來找到鏈表的中間節(jié)點(diǎn)廓啊。fast 指針每次移動兩步，而 slow 指針每次移動一步封豪。當(dāng) fast 指針到達(dá)鏈表末尾時(shí)谴轮，slow 指針會位于鏈表的中間。
• 反轉(zhuǎn)后半部分：從 slow 指針開始吹埠，反轉(zhuǎn)鏈表的后半部分第步。
• 檢查是否為回文：從鏈表的頭部和反轉(zhuǎn)后半部分的頭部開始，同時(shí)遍歷并比較每個(gè)節(jié)點(diǎn)缘琅。如果所有節(jié)點(diǎn)都相等粘都，那么鏈表就是一個(gè)回文。
• （可選）恢復(fù)鏈表：如果需要將鏈表恢復(fù)到原始狀態(tài)刷袍，你需要再次反轉(zhuǎn)其后半部分翩隧。

這個(gè)方法的時(shí)間復(fù)雜度是 O(n)，空間復(fù)雜度是 O(1)呻纹，符合題目的 Follow-up 要求堆生。

160. 相交鏈表

主要目標(biāo)是找到兩個(gè)鏈表的交點(diǎn)。解題關(guān)鍵是使用兩個(gè)指針雷酪，一個(gè)從第一個(gè)鏈表的頭部開始淑仆，另一個(gè)從第二個(gè)鏈表的頭部開始。

兩個(gè)鏈表有相交太闺，那么他們對接起來后最后幾位肯定一樣糯景。

- 鏈表 A: a1 → a2 → c1 → c2 → c3 → null (長度 5)
- 鏈表 B: b1 → b2 → b3 → c1 → c2 → c3 → null (長度 6)


- a1 a2 c1 c2 c3 b1 b2 b3 c1 c2 c3
- b1 b2 b3 c1 c2 c3 a1 a2 c1 c2 c3

1. 首先，兩個(gè)指針分別從各自的鏈表頭開始遍歷省骂。
2. 當(dāng)一個(gè)指針到達(dá)其鏈表的末尾時(shí)蟀淮，將它重置到另一個(gè)鏈表的頭部。
3. 如果兩個(gè)鏈表相交钞澳，兩個(gè)指針最終會在交點(diǎn)處相遇怠惶。

這種方法的優(yōu)點(diǎn)是時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)轧粟。這里的 n 是兩個(gè)鏈表中總節(jié)點(diǎn)數(shù)策治。

這樣做的目的是讓兩個(gè)指針走過相同數(shù)量的節(jié)點(diǎn)脓魏，從而能在交點(diǎn)（如果存在）處相遇。

92. 反轉(zhuǎn)鏈表-ii

1. 指針：您需要多個(gè)指針來跟蹤列表的不同部分通惫，例如子部分之前的最后一個(gè)節(jié)點(diǎn)茂翔，子部分內(nèi)的第一個(gè)和最后一個(gè)節(jié)點(diǎn)以及子部分之后的節(jié)點(diǎn)。

2. 反轉(zhuǎn)子部分：您可以使用標(biāo)準(zhǔn)的鏈表反轉(zhuǎn)技術(shù)（交換相鄰節(jié)點(diǎn)的“next”指針）來反轉(zhuǎn)目標(biāo)子部分中的節(jié)點(diǎn)履腋。

3. 重新連接：在反轉(zhuǎn)后珊燎，您需要正確地重新連接子部分之前的最后一個(gè)節(jié)點(diǎn)到子部分的新第一個(gè)節(jié)點(diǎn)，以及反轉(zhuǎn)后的子部分的最后一個(gè)節(jié)點(diǎn)到其后面的第一個(gè)節(jié)點(diǎn)遵湖。

4. 虛擬節(jié)點(diǎn)：使用虛擬節(jié)點(diǎn)可以簡化處理邊緣情況悔政，例如當(dāng)(m)為1時(shí)。

5. 時(shí)間復(fù)雜度：此操作可以在(O(n))時(shí)間內(nèi)完成延旧，其中(n)是列表的長度谋国，因?yàn)槲覀冎恍柰ㄟ^該列表進(jìn)行一次遍歷。

6. 空間復(fù)雜度：空間復(fù)雜度為(O(1))迁沫，因?yàn)槲覀冎恍枰潭〝?shù)量的指針芦瘾。

最后返回 `dummy.next`，即整個(gè)鏈表的新頭節(jié)點(diǎn)弯洗。

舉例 12345 2,4 14325 而且我也知道 preStart.next.next = cur 是為了把 2后面接上5 preStart.next = prev 是為了把 1 后面接上4 但是我實(shí)在不能理解他是如何明確接的節(jié)點(diǎn)和位置旅急。

這里的關(guān)鍵在于 `preStart.next` 和 `preStart.next.next` 這兩個(gè)指針逢勾。

1. `preStart.next` 一直指向要翻轉(zhuǎn)的子鏈表的第一個(gè)節(jié)點(diǎn)（在這個(gè)例子中是2）牡整。即使這個(gè)子鏈表被翻轉(zhuǎn)了，這個(gè)指針仍然會指向這個(gè)節(jié)點(diǎn)溺拱。
    
2. 當(dāng)子鏈表（2,3,4）被翻轉(zhuǎn)后逃贝，我們需要更新一下它與其他部分的連接。這就是 `preStart.next.next = cur` 和 `preStart.next = prev` 的作用迫摔。
    
3. `preStart.next.next = cur` 是將翻轉(zhuǎn)子鏈表的最后一個(gè)節(jié)點(diǎn)（現(xiàn)在是2）連接到剩下的部分（5）沐扳。因?yàn)?`cur` 在循環(huán)結(jié)束后指向5。
    
4. `preStart.next = prev` 是將翻轉(zhuǎn)子鏈表的第一個(gè)節(jié)點(diǎn)（現(xiàn)在是4）連接回主鏈表句占。因?yàn)?`prev` 在循環(huán)結(jié)束后指向4沪摄。

嗯好，我明白了第一步纱烘， preStart.next 一直指向2 所以 preStart.next.next 就是 2 的 next 要只想 5杨拐， 但是是怎么知道 cur 就是5的 因?yàn)樯厦娴谋闅v嗎。 第二個(gè)問題擂啥，當(dāng) 2 的next 指向5后哄陶， 我需要把 1 preStart 的 next 指向4，我是怎么知道 prev 就是4

1. 關(guān)于 `cur`：在循環(huán)結(jié)束時(shí)哺壶，`cur` 指向子鏈表最后一個(gè)元素（這里是4）的下一個(gè)元素（這里是5）屋吨。這是因?yàn)樵谘h(huán)的最后一步蜒谤，我們做了 `cur = next`，其中 `next = cur.next`至扰。
    
2. 關(guān)于 `prev`：循環(huán)每次迭代都會更新 `prev`鳍徽，使其指向當(dāng)前翻轉(zhuǎn)后的鏈表的第一個(gè)節(jié)點(diǎn)。因此敢课，循環(huán)結(jié)束后旬盯，`prev` 會指向翻轉(zhuǎn)子鏈表的第一個(gè)節(jié)點(diǎn)，這里就是4翎猛。
    

所以胖翰，這兩個(gè)指針在循環(huán)結(jié)束后自然就位于我們希望他們所在的位置。這就是為什么 `cur` 和 `prev` 可以用于更新鏈表連接的原因切厘。

142. 環(huán)形鏈表 II

通常使用Floyd的“烏龜和兔子”算法來解決萨咳。這個(gè)問題可以分為兩個(gè)部分：

1. 首先，確定鏈表中是否存在環(huán)疫稿∨嗨可以使用兩個(gè)速度不同的指針（通常稱為slow和fast），slow每次移動一步遗座，而fast每次移動兩步舀凛。如果存在環(huán)，兩個(gè)指針最終會在環(huán)內(nèi)的某個(gè)位置相遇途蒋。

2. 找到環(huán)的起始節(jié)點(diǎn)猛遍。當(dāng)兩個(gè)指針相遇后，將其中一個(gè)指針重新放到鏈表的頭部号坡，然后兩個(gè)指針以相同的速度（每次一步）前進(jìn)懊烤。當(dāng)它們再次相遇時(shí)，相遇點(diǎn)就是環(huán)的起始節(jié)點(diǎn)宽堆。

這個(gè)場景：

Head
  |
  v
O->O->O->...->O
               |
               v
               O   <--- Cycle Start
               |
               v
O<-------------O
^             /
|  (c-x)     /
|           /
|          /
|         /
|        /  (x)
|       /
|      /
v     v
O-----O   <--- Meeting point of slow & fast during the first phase

2(m+x) = m+x+nc, slow 走兩倍m+x === fast 走 m+x 加 n倍的c
m+x = nc 如果 n = 1 那么 m = c-x


1. 畫一個(gè)點(diǎn)腌紧，稱之為 "Head"。
2. 從這個(gè)點(diǎn)畫 \(m\) 個(gè)點(diǎn)（連在一起）畜隶，把最后一個(gè)點(diǎn)標(biāo)記為 "Cycle Start"壁肋。
3. 從 "Cycle Start" 畫一個(gè)圈，包含 \(c\) 個(gè)點(diǎn)來表示環(huán)籽慢。
4. 標(biāo)記 `slow` 和 `fast` 在環(huán)內(nèi)相遇的點(diǎn)浸遗，距離 "Cycle Start" 有 \(x\) 個(gè)點(diǎn)。

現(xiàn)在：

- 第一階段結(jié)束時(shí)嗡综，`slow` 在 \(m+x\) 位置乙帮，`fast` 在 \(m+x+nc\) 位置。
- 第二階段開始時(shí)极景，把 `slow` 移動回 "Head"察净。

假設(shè)環(huán)的長度是 \(c\)驾茴，`slow` 和 `fast` 在環(huán)內(nèi)相遇時(shí)，距離環(huán)的起點(diǎn) \(x\) 步氢卡。所以 `fast` 距離環(huán)的起點(diǎn)還有 \(c-x\) 步锈至。

現(xiàn)在，`slow` 從 "Head" 走 \(m\) 步到達(dá) "Cycle Start"译秦，同時(shí) `fast` 也走 \(m\) 步峡捡，由于它距離 "Cycle Start" 是 \(c-x\)，兩者加起來正好是一個(gè)環(huán)的長度 \(c\)筑悴，所以它們會在 "Cycle Start" 相遇们拙。

1. 從`Head`到`Cycle Start`的距離為`m`。
2. `Cycle Start`就是環(huán)開始的地方阁吝。
3. 環(huán)內(nèi)的點(diǎn)數(shù)為`c`砚婆。
4. 當(dāng)`slow`和`fast`第一次在環(huán)內(nèi)相遇時(shí)，他們之間的距離是`x`突勇。
5. 環(huán)的其余部分（即從相遇點(diǎn)到`Cycle Start`）的距離是`c-x`装盯。

在第二階段，`slow`從`Head`開始甲馋，而`fast`從相遇點(diǎn)開始埂奈，它們都每次只走一步。當(dāng)`slow`走了`m`步到達(dá)`Cycle Start`時(shí)定躏，`fast`也正好走了`m`步账磺，加上它原本距離`Cycle Start`的`c-x`步，總共走了`m + (c-x)`步共屈，這正好是一個(gè)完整的環(huán)的長度绑谣，所以它們在`Cycle Start`處相遇。

希望這個(gè)“圖”能幫助你理解這個(gè)問題拗引！

146. LRU緩存

兩個(gè)主要操作：

1. get(key): 獲取指定 key 的值。如果 key 不存在幌衣，則返回 -1矾削。
2. put(key, value): 插入或更新一個(gè)鍵值對。如果緩存達(dá)到了容量上限豁护，需要移除最近最少使用的鍵值對哼凯。

解題思路：

1. 使用一個(gè) Map 對象存儲鍵值對。Map 保證了元素的插入順序楚里，這對于實(shí)現(xiàn) LRU 算法很有幫助断部。
2. 為了跟蹤緩存的容量，設(shè)定一個(gè) capacity 變量班缎。
3. 在 get() 方法中蝴光，如果 key 存在她渴，返回對應(yīng)的值并更新其在 Map 中的位置（把它移到最后）。
4. 在 put() 方法中蔑祟，首先檢查 key 是否已存在趁耗。如果存在，先刪除舊的鍵值對疆虚。然后檢查緩存是否滿了苛败，如果滿了，移除最舊的（即最前面的）元素径簿。最后罢屈，添加新的鍵值對。