算法通俗講解推薦閱讀
【算法–鏈表】83.刪除排序鏈表中的重復元素–通俗講解
【算法–鏈表】刪除排序鏈表中的重復元素 II–通俗講解
【算法–鏈表】86.分割鏈表–通俗講解
【算法】92.翻轉鏈表Ⅱ–通俗講解
【算法–鏈表】109.有序鏈表轉換二叉搜索樹–通俗講解
【算法–鏈表】114.二叉樹展開為鏈表–通俗講解
【算法–鏈表】116.填充每個節點的下一個右側節點指針–通俗講解
【算法–鏈表】117.填充每個節點的下一個右側節點指針Ⅱ–通俗講解
【算法–鏈表】138.隨機鏈表的復制–通俗講解
【算法】143.重排鏈表–通俗講解
【算法–鏈表】146.LRU緩存–通俗講解
【算法–鏈表】147.對鏈表進行插入排序–通俗講解
【算法】【鏈表】148.排序鏈表–通俗講解
通俗易懂講解“相交鏈表”算法題目
一、題目是啥？一句話說清
給定兩個單鏈表，找出它們相交的起始節點；如果不存在相交節點，返回null。
示例：
- 輸入：鏈表A: 4→1→8→4→5，鏈表B: 5→6→1→8→4→5（相交于節點8）
- 輸出：節點8
二、解題核心
使用雙指針法，兩個指針分別從兩個鏈表的頭開始遍歷，當指針到達鏈表末尾時，切換到另一個鏈表的頭部繼續遍歷。如果鏈表相交，指針會在相交節點相遇；否則，會同時到達null。
這就像兩個人分別從兩個鏈表的起點開始走，如果走完自己的鏈表后走對方的鏈表，那么他們會在相交點相遇，因為兩人走過的總長度相同。
三、關鍵在哪里？（3個核心點）
想理解并解決這道題，必須抓住以下三個關鍵點：
1. 指針的路徑交換
- 是什么：當指針遍歷到鏈表末尾時，立即切換到另一個鏈表的頭部繼續遍歷。
- 為什么重要：這樣確保了每個指針都遍歷了兩個鏈表的全部節點，總長度相同，從而在相交點相遇。
2. 相遇條件
- 是什么：如果兩個鏈表相交，指針會在相交節點相遇；如果不相交，指針會同時到達null。
- 為什么重要：這是算法正確性的基礎。相遇時返回節點，否則返回null。
3. 處理長度差異
- 是什么：兩個鏈表長度可能不同，但通過交換路徑，指針走過的總長度相同（m+n）。
- 為什么重要：無需計算鏈表長度，直接遍歷即可處理長度差異，使算法簡潔高效。
四、看圖理解流程（通俗理解版本）
假設鏈表A: 4→1→8→4→5，鏈表B: 5→6→1→8→4→5，相交于節點8。
- 初始化：指針pA指向鏈表A的頭（節點4），指針pB指向鏈表B的頭（節點5）。
- 第一輪遍歷：
- pA遍歷A：4→1→8→4→5→null，然后切換到鏈表B的頭（節點5）。
- pB遍歷B：5→6→1→8→4→5→null，然后切換到鏈表A的頭（節點4）。
- 第二輪遍歷：
- pA從鏈表B的頭開始：5→6→1→8
- pB從鏈表A的頭開始：4→1→8
- 當pA走到節點8時，pB也走到節點8，兩者相遇，返回節點8。
如果不相交，例如鏈表A: 1→2→3，鏈表B: 4→5，則：
- pA遍歷：1→2→3→null→切換到B的頭（4→5→null）
- pB遍歷：4→5→null→切換到A的頭
