LinkList 總結
#clippings
鏈表的理論基礎
在這篇文章關於鏈表，你該瞭解這些！ (opens new window)中，介紹了如下幾點：
- 鏈表的種類主要為：單鏈表，雙鏈表，循環鏈表
- 鏈表的存儲方式：鏈表的節點在內存中是分散存儲的，通過指針連在一起。
- 鏈表是如何進行增刪改查的。
- 數組和鏈表在不同場景下的性能分析。
可以說把鏈表基礎的知識都概括了，但又不像教科書那樣的繁瑣。
鏈表經典題目
虛擬頭結點
在鏈表：聽說用虛擬頭節點會方便很多？ (opens new window)中，我們講解了鏈表操作中一個非常總要的技巧：虛擬頭節點。
鏈表的一大問題就是操作當前節點必須要找前一個節點才能操作。這就造成了，頭結點的尷尬，因為頭結點沒有前一個節點了。
每次對應頭結點的情況都要單獨處理，所以使用虛擬頭結點的技巧，就可以解決這個問題。
在鏈表：聽說用虛擬頭節點會方便很多？ (opens new window)中，我給出了用虛擬頭結點和沒用虛擬頭結點的代碼，大家對比一下就會發現，使用虛擬頭結點的好處。
鏈表的基本操作
在鏈表：一道題目考察了常見的五個操作！ (opens new window)中，我們通設計鏈表把鏈表常見的五個操作練習了一遍。
這是練習鏈表基礎操作的非常好的一道題目，考察了：
- 獲取鏈表第index個節點的數值
- 在鏈表的最前面插入一個節點
- 在鏈表的最後面插入一個節點
- 在鏈表第index個節點前面插入一個節點
- 刪除鏈表的第index個節點的數值
可以說把這道題目做了，鏈表基本操作就OK了，再也不用擔心鏈表增刪改查整不明白了。
這裡我依然使用了虛擬頭結點的技巧，大家複習的時候，可以去看一下代碼。
反轉鏈表
在鏈表：聽說過兩天反轉鏈表又寫不出來了？ (opens new window)中，講解了如何反轉鏈表。
因為反轉鏈表的代碼相對簡單，有的同學可能直接背下來了，但一寫還是容易出問題。
反轉鏈表是面試中高頻題目，很考察面試者對鏈表操作的熟練程度。
我在文章 (opens new window)中，給出了兩種反轉的方式，迭代法和遞歸法。
建議大家先學透迭代法，然後再看遞歸法，因為遞歸法比較繞，如果迭代還寫不明白，遞歸基本也寫不明白了。
可以先通過迭代法，徹底弄清楚鏈表反轉的過程！
刪除倒數第N個節點
在鏈表：刪除鏈表倒數第N個節點，怎麼刪？ (opens new window)中我們結合虛擬頭結點 和 雙指針法來移除鏈表倒數第N個節點。
鏈表相交
鏈表：鏈表相交 (opens new window)使用雙指針來找到兩個鏈表的交點（引用完全相同，即：內存地址完全相同的交點）
環形鏈表
在鏈表：環找到了，那入口呢？ (opens new window)中，講解了在鏈表如何找環，以及如何找環的入口位置。
這道題目可以說是鏈表的比較難的題目了。 但代碼卻十分簡潔，主要在於一些數學證明。
總結
這個圖是 代碼隨想錄知識星球 (opens new window) 成員：海螺人 (opens new window)，所畫，總結的非常好，分享給大家。
考察鏈表的操作其實就是考察指針的操作，是面試中的常見類型。
鏈表篇中開頭介紹鏈表理論知識 (opens new window)，然後分別通過經典題目介紹了如下知識點：
- 關於鏈表，你該瞭解這些！ (opens new window)
- 虛擬頭結點的技巧 (opens new window)
- 鏈表的增刪改查 (opens new window)
- 反轉一個鏈表 (opens new window)
- 刪除倒數第N個節點 (opens new window)
- 鏈表相交 (opens new window)
- 有否環形，以及環的入口 (opens new window)
上次更新：: 11/4/2022, 12:07:01 PM