题目描述
输入两个链表,找出它们的第一个公共结点。
当不存在公共节点时,返回空节点。
样例
给出两个链表如下所示:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
输出第一个公共节点c1
算法2
思路:
A链表指针p往前走,走到NULL后,p指向headB, 把B链表走一遍。
同理B链表q指针走到NULL后,q指向headA,把A链表走一遍
若AB相交,则p,q一定相遇。 若AB不相交,则p,q 最后一定都为NULL
时间复杂度 $O(2n)$
参考文献
C++ 代码
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;
}
};