题目描述
输入两个链表,找出它们的第一个公共结点。
当不存在公共节点时,返回空节点。
数据范围
链表长度 [1,2000]。
样例
给出两个链表如下所示:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
输出第一个公共节点c1
算法1
(y总巧妙写法)
A走完走B,B走完走A
C++ 代码
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB)
{
if(!headA || !headB) return nullptr;
for(auto pa = headA, pb = headB;;)
{
if(pa == pb) return pa;
if(pa) pa = pa->next;
else pa = headB;
if(pb) pb = pb->next;
else pb = headA;
}
}
};
算法2
(自己写法)
分别计算两个链表的长度,然后长链表先走,对齐后短链表再走
C++ 代码
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB)
{
int legA =0;
int legB =0;
for(auto p = headA;p;)
{
legA++;
p=p->next;
}
for(auto p = headB;p;)
{
legB++;
p = p->next;
}
//让A或B先走几个点
if(legA>legB)
{
for(int i=1;i<= legA -legB;++i) headA= headA->next;
}
else
{
for(int i=1;i<= legB -legA;++i) headB= headB->next;
}
for(auto pA = headA, pB=headB;pA;)
{
if(pA == pB) return pA;
pA = pA->next;
pB = pB->next;
}
return nullptr;
}
};