题目描述
输入两个链表,找出它们的第一个公共结点。
当不存在公共节点时,返回空节点。
样例
给出两个链表如下所示:
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
输出第一个公共节点c1
思路:用两个指针p,q分别指向A,B的链表头,当p!=q时进行循环,如果不为NULL,则向前一步,如果为NULL则跳到另一个链表头(p到B链表头,q到A链表头),然后再继续循环,直到p==q。(p==q有两种情况,链表交汇点或者都到链表尾)。如果链表交汇,记A,B各自非公共部分长度a,b,公共部分长度为c,则当p,q各自都走了a(/b)步或者a+b+c步时一定会相遇,相遇点就是链表的第一个公共节点。若链表A,B无交点,设它们的长度为a,b,那么当p,q走了a(/b)步或者a+b步时,它们会都为NULL。代码如下。
C++ 代码
/**
* 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;
while(p!=q){
if(p) p=p->next;
else p=headB;
if(q) q=q->next;
else q=headA;
}
return p;
}
};