一、題目要求
題目：給定兩條單鏈表 headA、headB，找出它們相交的起始節點（節點對象相同而非數值相等）。若無交點返回 null。
限制：鏈表無環；函數返回后鏈表結構不能被破壞。
圖示兩個鏈表在節點 c1 開始相交：
題目數據 保證 整個鏈式結構中不存在環。
注意，函數返回結果后，鏈表必須 保持其原始結構 。
示例 1：
示例 2：
示例 3：
二、解法 1 —— “先求長度差 + 對齊再同步”（時間 O(m+n)，空間 O(1)）
1. 思路
- 先各自遍歷一次求出長度
lenA、lenB。 - 計算差值
d = |lenA - lenB|。 - 讓較長鏈先走
d步，剩余部分兩鏈長度一致。 - 兩指針同時前進，第一次相遇即交點；若最后都為
null則無交點。
2. C++代碼
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode* curA = headA;ListNode* curB = headB;int lenA = 0;int lenB = 0;int chazhi;while(curA){curA=curA->next;lenA++;}while(curB){curB=curB->next;lenB++;}chazhi = abs(lenA-lenB);curA = headA;curB = headB;if (lenA>lenB){for(int i =0;i<chazhi;i++){curA=curA->next;}while(curA){if(curA==curB){return curA;}curA=curA->next;curB=curB->next;}}else{for(int i =0;i<chazhi;i++){curB=curB->next;}while(curA){if(curA==curB){return curA;}curA=curA->next;curB=curB->next;}}return NULL;}
};三、解法 2 —— “雙指針互跳”（一次掃描更簡潔）
1. 關鍵思想
- 指針
pA從 A 鏈頭走到尾后 跳到 B 鏈頭； - 指針
pB從 B 鏈頭走到尾后 跳到 A 鏈頭； - 若存在交點，它們在第
lenA + lenB - k步會同時到達交點； - 若無交點，兩指針最終同時成為
nullptr，循環結束。
整體只走兩條鏈各一遍，總步數
lenA + lenB。
?2. C++代碼
class Solution {
public:ListNode* getIntersectionNode(ListNode* headA, ListNode* headB) {// 若有任何一條為空，必無交點if (!headA || !headB) return nullptr;ListNode* pA = headA; // 指針 AListNode* pB = headB; // 指針 B/* 只要不相等就一直走：* - pA 走完鏈 A 就跳到鏈 B 的頭* - pB 走完鏈 B 就跳到鏈 A 的頭* 最多 lenA+lenB 步，兩指針必同時為交點或同時為 nullptr*/while (pA != pB) {pA = (pA ? pA->next : headB); // 三元運算避免空指針訪問pB = (pB ? pB->next : headA);}return pA; // 返回交點或 nullptr}
};
四、兩種解法對比
| 指標 | 解法 1：先算長度差 | 解法 2：雙指針互跳 |
|---|---|---|
| 時間復雜度 | O(m + n) | O(m + n) |
| 額外空間 | O(1) | O(1) |
| 代碼行數 | 略長（需兩次遍歷 + 對齊） | 極簡 |
| 直觀難度 | ★★ | ★★★（第一次見需要理解“互跳”） |
| 常用場景 | 任何面試都能過 | 高頻高贊寫法，面試官更青睞 |
五、重要知識點
| 知識點 | 速記 |
|---|---|
| 比較節點地址 | 交點要判斷 指針是否相同，不能只比較 val |
| 虛擬頭 vs 不需要 | 本題不必修改原鏈結構，通常不加 dummy；若要改鏈可加 dummy |
| 時間下界 | 至少 O(m+n)，因為每節點都需被訪問 |
| 空間下界 | 題面要求 O(1)，因此不能用 set、vector 存節點 |
| 互跳原理 | 走完自己鏈就走對方鏈，總步數相等，長短差抵消 |
| 無交點情況 | 雙指針最終一起到 nullptr，返回 nullptr |
六、面試官常追問
-
帶環鏈表場景如何處理？
先用 Floyd 判環：- 若兩鏈一無環一有環 → 一定不相交；
- 若都無環：按本題思路；
- 若都同環：分“交點在環前”與“在環內”兩種討論。
-
能否用遞歸？
理論可行但會消耗O(m+n)遞歸棧，不推薦。 -
如果鏈表非常長（百萬級），但內存緊張，使用哪種算法？
互跳法依舊O(1)空間，非常適合。
)
)
)
