剑指 Offer 52. 两个链表的第一个公共节点（有情人终成眷属）

第一个公共节点（有情人终成眷属）"/>

剑指 Offer 52. 两个链表的第一个公共节点（有情人终成眷属）

题目

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

在节点 c1 开始相交。
LeetCode 剑指 Offer 52. 两个链表的第一个公共节点

思路

两个链表长度分别为L1+C、L2+C， C为公共部分的长度，第一个人走了L1+C步后，回到第二个人起点走L2步；第2个人走了L2+C步后，回到第一个人起点走L1步。 当两个人走的步数都为L1+L2+C时就两个家伙就相爱了（我酸了）

超时代码

class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode heada = headA, headb = headB;while (true) {if (headA == headB)return headA;headA = headA.next;headB = headB.next;if (headA == null)headA = headb;if (headB == null)headB = heada;}}
}

双百AC代码

class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode heada = headA, headb = headB;while (heada != headb) {heada = heada != null ? heada.next : headB;headb = headb != null ? headb.next : headA;}return heada;}
}

猛地一看好像两段代码区别不大，但实际上差之毫厘，谬以千里。两段代码的关键区别在于，当链表指针指向null的时，是否判断heada与headb相等。
第一段代码的错误在于当链表指针指向null的时，不判断heada与headb是否相等，直接指向另一个链表的表头。所以 第一段代码不能处理两个链表没有交集的情况。导致死循环。
当出现两个链表没有交集的情况时，在第二段代码中，两个链表指针最终都会指向null，并参与判断，跳出循环，返回null。