五種方法解決鏈表的第一個公共子節(jié)點問題
題目：劍指 Offer 52. 兩個鏈表的第一個公共節(jié)點
輸入兩個鏈表，找出它們的第一個公共節(jié)點。
如下面的兩個鏈表：
在節(jié)點 c1 開始相交。
鏈表節(jié)點的定義
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
小技巧：
如果題目剛拿到手的時候沒有思路怎么辦？
試著將常用的數(shù)據(jù)結(jié)構(gòu)和常用的算法思想都想一遍，一個一個靠，看有沒有能解決的。
常用的數(shù)據(jù)結(jié)構(gòu)：數(shù)組，鏈表，隊列，棧，Hash表，集合，樹，堆等等
常用的算法：各種排序，雙指針，遞歸等等
按照這個思路，想一想
（1）方法一： 首先想到的就是暴力破解，用一個雙層循環(huán)遍歷來一個一個對比找相同的那個節(jié)點，這樣時間復(fù)雜度就會有點高，O(n^2)
（2）方法二： 既然時間復(fù)雜度比較高的話，那我們就想想用空間換時間，數(shù)組？鏈表？隊列？棧？
欸，這個可以。既然兩個鏈表尾巴是一致的，那將兩個鏈表分別放到棧里面，根據(jù)棧先進(jìn)后出的特性，相當(dāng)于就是從尾到頭地遍歷鏈表嘛。
在出棧過程中，對比兩邊的節(jié)點，若相同則繼續(xù)出棧比較，若不相同，則上一個出棧的節(jié)點就是公共節(jié)點。
這樣時間復(fù)雜度就降到O(n)，空間復(fù)雜度為O(n)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 將鏈表A存放到棧A中
stack<ListNode*> stackA;
while (headA != nullptr) {
stackA.push(headA);
headA = headA->next;
}
// 將鏈表B存放到棧B中
stack<ListNode*> stackB;
while (headB != nullptr) {
stackB.push(headB);
headB = headB->next;
}
ListNode* intersectionNode = nullptr;
ListNode* tempA = nullptr;
ListNode* tempB = nullptr;
// 同時出棧進(jìn)行比較
while(!stackA.empty() && !stackB.empty()) {
tempA = stackA.top();
tempB = stackB.top();
stackA.pop();
stackB.pop();
// 當(dāng)遇到不一樣的節(jié)點時，證明上一個出棧的即為公共節(jié)點，就是當(dāng)前節(jié)點的下一個節(jié)點
if (tempA != tempB) {
break;
}
}
// 結(jié)束while的可能性有兩種：
// 1. 碰到了不同的節(jié)點
if(tempA != tempB) {
intersectionNode = tempA->next;
} else { // 2. A和B所有節(jié)點都是相同的，也就是棧A和棧B同時為空
intersectionNode = tempA;
}
return intersectionNode;
}
};
（3）方法三： 還有沒有其他的數(shù)據(jù)結(jié)構(gòu)能用呢？Hash表和集合？
可以，只將一個鏈表中的節(jié)點存到hash表或者集合中，然后遍歷另外一個鏈表，看有沒有集合中有沒有一樣的節(jié)點。
時間復(fù)雜度為O(n)，空間復(fù)雜度為O(n)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
set<ListNode*> setA;
while(headA != nullptr) {
setA.insert(headA);
headA = headA->next;
}
while (headB != nullptr) {
if (setA.find(headB) != setA.end()) {
return headB;
}
headB = headB->next;
}
return nullptr;
}
};
那還有沒有時間或者空間復(fù)雜度更低的方法呢？一般這個時候，想要的方法都是稍微帶一點技巧性了，多刷題的重要性在此時此刻就體現(xiàn)出來了。
（4）方法四： 拼接法，既然兩個鏈表最后的部分都是一樣的。那我們將兩個鏈表拼一下，就像A和B，我們拼成AB和BA兩種，然后進(jìn)行遍歷，最后肯定會在某一個節(jié)點達(dá)成相同的。
注意，我們是為了減少空間復(fù)雜度來跟進(jìn)一步地找方法的，如果我們又去新建兩個鏈表豈不是違背初衷了嘛？
那我們怎么辦呢？
欸，我們只需要在遍歷完A后，接著遍歷B，不就組成AB了。同樣遍歷B，再遍歷A，就組成BA了。而且，一邊遍歷一邊比較，這樣就OK啦！
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if (headA == nullptr || headB == nullptr) {
return nullptr;
}
ListNode* pA = headA;
ListNode* pB = headB;
// 當(dāng)不為公共節(jié)點時，就接著往下遍歷
while (pA != pB) {
pA = pA->next;
pB = pB->next;
/* 考慮邊界條件，那就是沒有公共節(jié)點的時候
* 在更新pA和pB之后，如果pA == pB == nullptr
* 就意味著AB和BA對比完了，那我們就不能繼續(xù)下去
* 否則會導(dǎo)致ABABABAB……和BABABABA……無限下去造成死循環(huán)了
* */
if (pA != pB) {
// 拼成AB，當(dāng)A遍歷完了，就接著遍歷B
if (pA == nullptr) {
pA = headB;
}
// 拼成BA，當(dāng)B遍歷完了，就接著遍歷A
if (pB == nullptr) {
pB = headA;
}
}
}
return pA;
}
};
（5）方法五： 對于鏈表而言，我們最常用的方法還有一個雙指針的方法。
既然兩個鏈表尾巴部分一樣，那就兩個指針一起開始遍歷嘛，如果同時遍歷到同一個節(jié)點，那不就是我們要找的第一個公共節(jié)點嘛。
但是要是像圖中這樣去遍歷，因為A和B長度不一樣，那pA和pB永遠(yuǎn)都不可能遍歷到同一個節(jié)點上嘛！
這個簡單啊，我們讓他們從同一起點出發(fā)不就好了，誰的跑道長，那我們就先讓誰先跑一點，保證兩個指針在同一起跑線就好啦！文章來源：http://www.zghlxwxcb.cn/news/detail-603242.html
文章來源地址http://www.zghlxwxcb.cn/news/detail-603242.html
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
// 遍歷A，得到A的長度
ListNode *pA = headA;
int lengthA = 0;
while(pA != nullptr) {
++lengthA;
pA = pA->next;
}
// 遍歷B，得到B的長度
ListNode *pB = headB;
int lengthB = 0;
while(pB != nullptr) {
++lengthB;
pB = pB->next;
}
pA = headA;
pB = headB;
// 計算長度差并統(tǒng)一起跑點
if(lengthA - lengthB > 0) {
int sub = lengthA - lengthB;
while(sub != 0) {
pA = pA->next;
--sub;
}
} else if (lengthB - lengthA > 0) {
int sub = lengthB - lengthA;
while(sub != 0) {
pB = pB->next;
--sub;
}
}
while(pA != nullptr && pB != nullptr) {
if (pA == pB) {
break;
}
pA = pA->next;
pB = pB->next;
}
return pA;
}
};
到了這里，關(guān)于算法通關(guān)村第一關(guān)——鏈表經(jīng)典問題之第一個公共子節(jié)點筆記的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
