题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

思路

我走过你来时的路，如果我们有交点，必然会相遇以后一起走。

当某个链表遍历完以后，让它去从头遍历另一个链表，如果有交点，那么他们一定会相遇，否则会同时走到null。

代码

public class Solution_160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode p1 = headA;
        ListNode p2 = headB;
        while (p1 != p2) {
            p1 = p1 != null ? p1.next : headB;
            p2 = p2 != null ? p2.next : headA;
        }
        return p1;
    }
}

注意：不能写成：

p1 = p1.next != null ? p1.next : headB;
p2 = p2.next != null ? p2.next : headA;

因为这样写会导致p1和p2永远取不到Null，但是，当两个链表没有交点时，他们最终会同时取到null从而退出循环。