相交链表

来源Leetcode第160题相交链表

编写一个程序，找到两个单链表相交的起始节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 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 个节点。

---

哈希表

遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表 B 中的每一个结点 b_ib**i 是否在哈希表中。若在，则 b_ib**i 为相交结点。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA == null || headB == null)
        return null;
    ListNode p1 = headA;
    Set<ListNode> map = new HashSet<>();
    while(p1 != null){
        map.add(p1);
        p1 = p1.next;
    }
    p1 = headB;
    while(p1 != null){
        if(map.contains(p1))
            return p1;
        else p1 = p1.next;
    }
    return null;
}

双指针

• 创建两个指针 pA 和 pB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。
• 当 pA到达链表的尾部时，将它重定位到链表 B 的头结点 (你没看错，就是链表 B); 类似的，当 pB 到达链表的尾部时，将它重定位到链表 A 的头结点。
• 若在某一时刻 pA和 pB 相遇，则 pA/pB为相交结点。
• 想弄清楚为什么这样可行, 可以考虑以下两个链表: A={1,3,5,7,9,11} 和 B={2,4,9,11}，相交于结点 9。 由于 B.length (=4) < A.length (=6)，pB比 pA少经过 22 个结点，会先到达尾部。将 pB 重定向到 A 的头结点，pA 重定向到 B 的头结点后，pB 要比 pA 多走 2 个结点。因此，它们会同时到达交点。
• 如果两个链表存在相交，它们末尾的结点必然相同。因此当 pA/pB 到达链表结尾时，记录下链表 A/B 对应的元素。若最后元素不相同，则两个链表不相交。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA == null || headB == null)
        return null;
    ListNode pa = headA , pb = headB;
    while(pa != pb){
        pa = pa == null ? headB : pa.next;
        pb = pb == null ? headA : pb.next;
    }
    return pa;
}