1籽御、題目描述
輸入兩個鏈表枚尼，找出它們的第一個公共結(jié)點留搔。
當(dāng)不存在公共節(jié)點時更胖，返回空節(jié)點。
樣例
給出兩個鏈表如下所示：
A： ? a1 → a2
? ? ? ? ? ? ↘
? ? ? ? ? ? ? c1 → c2 → c3
? ? ? ? ? ? ↗
B: b1 → b2 → b3輸出第一個公共節(jié)點c1
2隔显、問題描述：
3却妨、問題關(guān)鍵：
- 如果有公共結(jié)點肯定是在后面重疊，且后面部分都是共同的括眠。
- 方法1：先計算出兩個鏈表的長度彪标，可以讓比較長的先走兩個鏈表長度之差的步數(shù)，兩個再一起走掷豺。
- 方法2：不同部分為a捞烟， 和b薄声，公共部分為c；a + c + b = b + c + a;讓兩個一起走题画，a走到頭就轉(zhuǎn)向b默辨， b走到頭轉(zhuǎn)向a，則在公共部分相遇婴程。
4廓奕、C++代碼：
方法1:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
auto p = headA, q = headB;
int la = 0, lb = 0;
for (auto t = headA; t; t = t->next) la ++;
for (auto t = headB; t; t = t->next) lb ++;
int k = la - lb;
if (la < lb) {
p = headB, q = headA;
k = lb - la;
}
while(k --) {
p = p->next;
}
while(p) {
if (p == q) return p;
p = p->next;
q = q->next;
}
return nullptr;
}
};
方法2:
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
auto p = headA, q = headB;
while(p != q) {
if(p) p = p->next;
else p = headB;
if (q) q = q->next;
else q = headA;
}
return p;
}
};
