AcWing 66. 两个链表的第一个公共结点
题目
输入两个链表，找出它们的第一个公共结点。
当不存在公共节点时，返回空节点。
数据范围
链表长度[1,2000]。
样例
给出两个链表如下所示：
A： a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
输出第一个公共节点c1
备注
第一个公共结点的含义
第一个公共结点，即这个结点后的所有结点相等。
也就是出现第一个公共结点后，从此结点开始到链表结尾，两链表的结点数量一致，结点内容也一致。
本题调试框内输入输出的含义
如果大家打算在调试框内构造输入输出，格式如下：
输入包括三行，例如：
[a, b, c, d, e]
[f, g, h]
3
表示的两个链表分别是：
- 第一个链表即输入第一行的链表：
[a, b, c, d, e] - 第二个链表即将输入第二行的链表接到第一行链表的第3个节点后面（链表节点下标从1开始）：
[a, b, c, f, g, h] - 如果输入第三行为-1，表示两个链表不相交，此时第二个链表即输入第二行的链表：
[f, g, h]
输出包括一行：
- 如果两个链表相交，则输出相交节点的权值，即
c； - 如果不相交，则输出
null
巧妙的思路
一共有两种情况，第一种情况是两个链表存在公共结点，第二种情况是两个链表不存在公共结点。
如图所示，我们定义两个指针p、q，同时定义每一个指针的路线，其中：
- p指针从第一个链表的起点出发，到达第一个链表尾部(即空结点)后，转到第二个链表起点继续前进，直到和q指针相遇为止(也就是p和q相等)
- q指针从第二个链表的起点出发，到达第二个链表尾部(即空结点)后，转到第一个链表起点继续前进，直到和p指针相遇为止(也就是p和q相等)
我们将距离分别设置为如图所示的a、b、c，那么:
- 当两个链表存在公共结点时，两个指针p、q走过的路径长度分别为：
a+c+b、b+c+a，走过的总长度相同。 - 当两个链表不存在公共结点时，两个指针p、q走过的路径长度分别为：
a+b、b+a
题解
/**
* 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) {
p = p ? p->next : headB;
q = q ? q->next : headA;
}
return p;
}
};