兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)

問題描述

給定兩個(gè)無環(huán)的單向鏈表，找到它們的第一個(gè)公共節(jié)點(diǎn)。如果沒有公共節(jié)點(diǎn)，則返回空。

要求：

• 空間復(fù)雜度： $O(1)$
• 時(shí)間復(fù)雜度： $O(n)$
• 數(shù)據(jù)范圍： 鏈表長度 $n\le 1000$

輸入數(shù)據(jù)分為三個(gè)部分：

1. 第一個(gè)鏈表的非公共部分。
2. 第二個(gè)鏈表的非公共部分。
3. 兩個(gè)鏈表的公共部分。

后臺(tái)會(huì)根據(jù)輸入組裝成兩個(gè)單鏈表，傳入FindFirstCommonNode函數(shù)，返回第一個(gè)公共節(jié)點(diǎn)。

---

示例說明

示例 1

輸入：
{1,2,3}, {4,5}, {6,7}

鏈表結(jié)構(gòu)：
第一個(gè)鏈表：1 -> 2 -> 3 -> 6 -> 7
第二個(gè)鏈表：4 -> 5 -> 6 -> 7

輸出：
{6,7}

說明：
兩個(gè)鏈表從節(jié)點(diǎn)值為 6 的位置開始公共，返回節(jié)點(diǎn)值為 6 的節(jié)點(diǎn)。

---

示例 2

輸入：
{1}, {2,3}, {}

鏈表結(jié)構(gòu)：
第一個(gè)鏈表：1
第二個(gè)鏈表：2 -> 3

輸出：
{}

說明：
兩個(gè)鏈表沒有公共節(jié)點(diǎn)，返回 null。

---

方法及實(shí)現(xiàn)

方法描述

采用雙指針法：

1. 設(shè)置兩個(gè)指針 first 和 second 分別指向兩個(gè)鏈表的頭節(jié)點(diǎn)。
2. 當(dāng) first 和 second 不相等時(shí)，指針逐步向后移動(dòng)：
   • 如果某個(gè)指針到達(dá)鏈表尾部，則跳轉(zhuǎn)到另一個(gè)鏈表的頭部。
   • 如果兩個(gè)指針在某節(jié)點(diǎn)相遇，則該節(jié)點(diǎn)為第一個(gè)公共節(jié)點(diǎn)。
   • 如果兩指針遍歷結(jié)束仍未相遇，則無公共節(jié)點(diǎn)，返回 NULL。

代碼實(shí)現(xiàn)

struct ListNode* FindFirstCommonNode(struct ListNode* pHead1, struct ListNode* pHead2) {if (pHead1 == NULL || pHead2 == NULL) {return NULL;  // 如果任何一個(gè)鏈表為空，直接返回 NULL}struct ListNode* first = pHead1;  // 指針 first 初始指向鏈表1頭部struct ListNode* second = pHead2;  // 指針 second 初始指向鏈表2頭部// 當(dāng)兩個(gè)指針不相等時(shí)，繼續(xù)循環(huán)while (first != second) {first = (first != NULL) ? first->next : pHead2;  // 如果 first 到達(dá)末尾，跳轉(zhuǎn)到鏈表2頭部second = (second != NULL) ? second->next : pHead1;  // 如果 second 到達(dá)末尾，跳轉(zhuǎn)到鏈表1頭部}return first;  // 返回第一個(gè)公共節(jié)點(diǎn)或 NULL
}

---

復(fù)雜度分析

1. 時(shí)間復(fù)雜度：

   • 每個(gè)指針最多遍歷兩個(gè)鏈表的長度，總時(shí)間復(fù)雜度為 $O(n+m)$，其中 $n$ 和 $m$ 分別是兩個(gè)鏈表的長度。

2. 空間復(fù)雜度：

   • 只使用了兩個(gè)指針，空間復(fù)雜度為 $O(1)$。

---

示例運(yùn)行過程

示例 1

輸入：{1,2,3}, {4,5}, {6,7}
鏈表1：1 -> 2 -> 3 -> 6 -> 7
鏈表2：4 -> 5 -> 6 -> 7

• 初始：first 指向 1，second 指向 4。
• 第一次遍歷：first 和 second 分別遍歷各自鏈表，到達(dá)尾部后跳轉(zhuǎn)到另一鏈表頭部。
• 第二次遍歷：first 和 second 在節(jié)點(diǎn) 6 相遇。
• 輸出：{6,7}。

---

示例 2

輸入：{1}, {2,3}, {}
鏈表1：1
鏈表2：2 -> 3

• 初始：first 指向 1，second 指向 2。
• 第一次遍歷：first 遍歷到尾部后跳轉(zhuǎn)到鏈表2頭部，second 遍歷到尾部后跳轉(zhuǎn)到鏈表1頭部。
• 第二次遍歷：first 和 second 均到達(dá)尾部（NULL）。
• 輸出：{}。

---

總結(jié)

• 雙指針法通過交替遍歷鏈表，保證了時(shí)間復(fù)雜度 $O(n+m)$，且額外空間復(fù)雜度為 $O(1)$。
• 代碼簡單高效，能夠準(zhǔn)確找到第一個(gè)公共節(jié)點(diǎn)或判定無公共節(jié)點(diǎn)。

備注

最開始我寫的代碼是這樣的

while (first!=second) {if(first->nex!=NULL)first= first->next;else first= pHead2;if(second->next!=NULL)second= second->next;else second= pHead1;}

結(jié)果發(fā)現(xiàn)有問題，如果兩個(gè)不相交的鏈表，改成下面的才正確

while (first!=second) {if(first->next!=NULL)first= first->next;else first= pHead2;if(second->next!=NULL)second= second->next;else second= pHead1;}

思考了下原因，原來是如果按照舊的代碼， if(first->next!=NULL)，那么說明當(dāng)前是隊(duì)尾，使用 first= first->next;相當(dāng)于第一個(gè)把第二個(gè)連起來了，兩個(gè)隊(duì)列相互首位相連，原本不
else first= pHead2;