问题描述

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

示例 1：

输入： intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出： Reference of the node with value = 8
输入解释： 相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

解题报告

两个指针 node1, node2分别从两个链表头 headA，headB 开始出发，当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点，node2同理。

则当这两个指针相遇时所处的节点即为所求。

转自题解区答案，这种做法太巧秒了。。。。

实现时需要注意的一点是：

node1=node1?node1->next:headB;

而不是：

node1=node1->next?node1->next:headB;

如果这样写，当两个链表没有公共节点时，答案为 null，但是 node1 无法取到 null，所以无法跳出循环。

实现代码

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {ListNode * node1=headA, *node2=headB;while(node1!=node2){node1=node1?node1->next:headB;node2=node2?node2->next:headA;}return node1;}
};

参考资料

[1] Leetcode 面试题52.两个链表的第一个公共节点
[2] 题解区：腐烂的橘子