题解 | #两个链表的第一个公共结点#
两个链表的第一个公共结点
http://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46
题意：
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。
方法一：
直接暴力
思路：二重循环遍历。如果找到公共节点，则返回。找不到，则return null
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
ListNode *p1,*p2;
for(p1=pHead1;p1!=nullptr;p1=p1->next){
for(p2=pHead2;p2!=nullptr;p2=p2->next){
if(p1==p2){//如果找到公共节点，则返回
return p1;
}
}
}
return nullptr;//找不到，return null
}
};
时间复杂度：%2Cn%E6%98%AF%E9%93%BE%E8%A1%A8%E9%95%BF%E5%BA%A6%E3%80%82)
空间复杂度：%2C%E4%B8%8D%E9%9C%80%E8%A6%81%E9%A2%9D%E5%A4%96%E7%A9%BA%E9%97%B4%E3%80%82)
方法二：
双指针
思路：利用双指针，及其不同链表长度和循环来实现。如下图：
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
ListNode *p1=pHead1,*p2=pHead2;
while(p1!=p2){
p1=(p1==nullptr?pHead1:p1->next);
p2=(p2==nullptr?pHead2:p2->next);
}
return p1;
}
}; 时间复杂度：%2Cn%E6%98%AF%E5%BE%AA%E7%8E%AF%E6%AC%A1%E6%95%B0%E3%80%82)
空间复杂度：
海康威视公司氛围 407人发布
