一天，朋友胃疼的難受，陪他去醫院
醫生：這些天你都吃了什麼？
朋友：媳婦剩的飯我吃，孩子剩的飯我也吃
醫生：你家不養狗的嗎？
朋友：難道狗剩下的我也要吃？
我當場就笑岔氣了
關于什麼是連結清單，本文不做過多介紹，不了解的小夥伴自行去充能
稍微帶大家回顧下連結清單的分類，不做過多介紹，直接看圖
單向循環連結清單
雙向循環連結清單
由單連結清單 + 單向循環連結清單組成
後續的場景都會基于某些特定類型的連結清單，大家不要太放飛自我
我也會在各個場景中明确指明基于那個類型，大家不要看偏了
單向節點 OneWayNode
雖然代碼用 java 實作，但涉及到的算法實作是通用的，希望大家不要被開發語言所禁锢
基本上指的是單連結清單的反轉，大家就認為是單連結清單的反轉
樓主在以往的面試過程中就遇到過這個問題，而且不止一次被面到
如果大家連這個都不會，趕緊偷摸 code 起來
遞歸實作，實作簡單，也好了解
有遞歸，往往有其相愛相殺的疊代
不管是遞歸還是疊代，變量指派的順序不是随便的，不信你們改變下順序試試
如果沒有任何限制，反轉實作方式非常多；但面試時，往往會對時間複雜度或空間複雜度做一個極緻的考量
這道題如果出現在面試中，那麼考核點就是：時間複雜度 O(N) ，額外空間複雜度 O(1) ，那麼你們覺得遞歸的實作會讓面試官滿意嗎？
實際開發工程中，反轉往往不需要大家手動去實作，進階程式設計語言基本都有已經實作好的工具方法，大家直接用就好
例如 java 中有工具方法： Collections.reverse ，有興趣的可以去跟下自己所用語言的實作，你會有驚喜，會發現有意思的新大陸
何謂回文，就是反轉之後與之前本身一樣，例如 a,b,b,a 、 1,2,3,2,1
針對該問題，大家第一時間想到的肯定是二分法，但二分法是基于數組的，它不适用于單連結清單
那麼如何判斷單連結清單的回文了
那就按回文的描述那樣，對原連結清單進行拷貝，然後反轉拷貝的連結清單，再将原連結清單與新連結清單的值逐一對應比較，過程類似如下
代碼如下
有個資料結構，先進後出，也适用于這個場景，這個資料結構就是：棧；直接上代碼
利用棧的方式，可以優化，其實隻需要入棧連結清單右半側的資料即可
如何控制隻入棧連結清單右半側的資料了，需要用到快慢指針
快慢指針的起點都是頭結點，慢指針每次移動一個，快指針一次移動兩個，當快指針走完的時候，慢指針來到中間位置
将慢指針所在的連結清單元素以及慢指針之後的連結清單元素入棧
上述的三種方式，不管是哪一種，額外空間複雜度都是 O(N) ，那有沒有額外空間複雜度為 O(1) 的方式了
有，同樣用快慢指針，隻是快指針走完後，慢指針以及它之後的連結清單元素不是入棧，而是反轉，将反轉後的連結清單與原連結清單逐一對應比較，如下圖所示
代碼實作
除了有限幾個變量，沒有使用額外的空間，那麼額外空間複雜度就是 O(1)
給定一個單向連結清單（單連結清單或環形連結清單中的某一種），判斷它是否成環，不成環傳回 null ，成環則傳回入環的第一個節點
單連結清單傳回 null ，環形連結清單則傳回入環的第一個節點
對于題意，相信大家已經了解，那麼如何用代碼實作了？
借助 哈希表 ；周遊連結清單，将節點逐個放入 哈希表 ，放入的時候判斷節點是否已存在
若存在，那麼該節點就是入環的第一個節點，若不存在，則将節點放入 哈希表
如若連結清單能周遊完，則說明沒有成環，直接傳回 null
我們來看代碼
就結果而言是對的，但卻用了 O(N) 的額外空間複雜度，這往往不是面試官想要的，他想要的往往是 O(1) 的額外空間複雜度
有沒有什麼辦法可以做到了，肯定是有的： Floyd判圈算法
關于 Floyd判圈算法 ，大家自行去百度，它有一個結論：快慢指針第一次在環中相遇時，其中一個指針回到起點，然後兩個指針同時一次走一步向後移動，當它們再次相遇時，一定是在第一個入環節點
我們來簡單證明一下這個結論，如下圖
第一次相遇之前，慢指針一次走一步，快指針一次走兩步，那麼第一次相遇時，快指針走的距離 FD = p + f * c + m，慢指針所走的距離 SD = p + s * c + m
其中 f 表示快指針在環中走的完整圈數，s 表示慢指針在環中走的完整圈數
是以 FD = 2 * SD，則有 p + f * c + m = 2 * (p + s * c + m)，得到 p + m = (f - 2s) * c
f - 2s 肯定是一個 >= 0 的整數，是以 p + m 是環形周長的倍數
快慢指針第一次相遇後，快指針回到起點，慢指針停在相遇點（M），然後快慢指針都每次走一步向後移動
當快指針來到 P ，快指針走過的距離 FD = p，慢指針走過的距離 SD = p
因為慢指針是從 M 開始移動的，而 P 離 M 的距離為 m，是以相當于慢指針從 P 開始移動了 p + m 距離
而前面得出 p + m 就是環形周長的倍數，是以可以了解成慢指針從 P 開始，移動了環形周長倍數的距離，最終還是來到 P
是以快慢指針相遇于 P，也就是第一個入環節點
當了解了 Floyd判圈算法 後，代碼實作就很簡單了
僅僅用了快慢指針兩個額外變量，額外空間複雜度 O(1)
這個題其實還有一個變種：如果成環，請傳回環的大小（環中有多少個節點）
求環的大小比找入環的第一個節點要更好了解一點，當快慢指針在環中第一次相遇時，計時器初始成 0，一個指針不動，另一個指針逐漸向後移動
每移動一步計數器就加 1，當快慢指針再次相遇時，計數器的值就是環的大小；代碼就不示範了，大家自行去 code 、 code 、 code ！
給定兩個單向連結清單（單連結清單或環形連結清單），不相交則傳回 null ，相交則傳回相交的第一個節點
借助哈希表，實作比較簡單，也容易了解，直接看代碼
額外空間複雜度 O(N) ，這往往不是面試官想要的結果，那有沒有什麼方式，其額外空間複雜度是 O(1) 了，我們往下看
我們先來捋一下兩個單向連結清單的關系有哪些
如果兩個都是單連結清單，那麼他們之間的關系就隻有如下兩種
如果兩個單連結清單相交，那麼從第一個相交節點開始，後面的節點都是共用的
是以我們可以如下處理，先找到兩個連結清單的尾節點，如果這兩個尾節點不是同一個節點，那麼肯定不相交，直接傳回 null
找尾節點的過程中，記錄下兩個連結清單各自的長度：L1、L2，長的連結清單先移動 | L1-L2 |，然後兩個連結清單同時移動，一次移動一步
移動的過程中，一旦節點是同一個節點，那麼該節點就是相交的第一個節點，直接傳回該節點
結合代碼，更好了解
隻用到了有限的幾個變量，那麼額外空間複雜度 O(1)
因為連結清單節點是單向的，是以這兩個連結清單不可能相交
大家不要無限放大你們豐富的想象力，各種意淫這兩個連結清單的相交情況，結合實際情況去手動畫你們腦海中想象出來的相交情況
連結清單節點就一個 next 、一個 next 、一個 next ！
此時兩個連結清單的關系，無非就下面三種
兩個環形連結清單的三種情況其實都和入環節點有關系，假設 h1 的入環節點是 loop1，h2 的入環節點是 loop2
如果 loop1 == loop2，對應情況 2，此時相交的第一個節點肯定在 h1 ~ loop1 或 h2 ~ loop2 之間
我們可以把 h1 ~ loop1 看成一個單連結清單，h2 ~ loop2 看成第二個單連結清單
此時大家是不是想起了什麼，往上滑一滑，去看看 兩個單連結清單 的相交
如果 loop1 != loop2，對應情況 1、3
從 loop1 的下一個節點開始，一次走一步，如果回到了 loop1 還未遇到 loop2，那麼兩個連結清單不相交
如果回到 loop1 之前遇到了 loop2，那麼說明兩個連結清單相交，第一個相交的節點就是 loop1 或 loop2
我們來看看代碼
把 兩個單向連結清單 的三種關系串起來
額外空間複雜度 O(1)
有沒有覺得很好玩 ？
1、一個題的實作方式往往有多種，但面試中往往考核的是時間複雜度或空間複雜度的極緻利用
2、快慢指針在連結清單中很重要，希望大家能夠建立起快慢指針的概念
3、連結清單的花式玩法非常多，有興趣的可以去力扣上刷一刷：連結清單