1 题目描述
输入两个链表,找出它们的第一个公共结点。
当不存在公共节点时,返回空节点。
样例
给出两个链表如下所示:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
输出第一个公共节点c1
2 思路
- 创建两个指针,指针p指向A链表的第一个结点,指针q指向B链表的第一个结点
- 判断,p和q是否相等
- 相等,退出循环
- 不相等,p往后移动一位,q往后移动一位
- 当p为空的时候,指向B链表的第一个结点,当q为空的时候指向A链
的第一个结点
- 当p为空的时候,指向B链表的第一个结点,当q为空的时候指向A链
3 代码
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
ListNode* p = headA;
ListNode* q = headB;
while(p!=q)
{
if(!p) p = headB;
else p = p->next;
if(!q) q = headA;
else q = q->next;
}
return p;
}
};