面试题 02.07. 链表相交

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第k个节点与另一个链表的第j个节点是同一节点（引用完全相同），则这两个链表相交。

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

示例 2：

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

示例 3：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

注意：

• 如果两个链表没有交点，返回 null 。
• 在返回结果后，两个链表仍须保持原有的结构。
• 可假定整个链表结构中没有循环。
• 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

思路

分情况讨论：

• 如果链表中有一个是空的，那么直接返回 null。
• 如果链表末尾元素不一样，那么说明一定不会相交，所以也返回 null。
• 除去上面两种情况，就说明链表一定会相交。先计算两个链表的长度，并计算出长度差 n。然后较长的链表先移动 n 位，再两个链表一起移动，如果节点相等则为相交点

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    if(headA == null || headB == null){
        return null;
    }
    int lengthA = 0;
    int lengthB = 0;
    ListNode nodeA = headA;
    ListNode nodeB = headB;
    //获取ListA长度
    while(nodeA != null){
        nodeA = nodeA.next;
        lengthA++;
    }
    //获取ListB长度
    while(nodeB != null){
        nodeB = nodeB.next;
        lengthB++;
    }
    
    //判断终点是否相等
    if(nodeA != nodeB){
        return null;
    }
    
    //获取两条链表长度差n
    boolean langerA = lengthA >= lengthB;
    int n = langerA ? lengthA - lengthB : lengthB - lengthA;
    
    //较长的链表先移动n位
    while(langerA && n > 0){
        headA = headA.next;
        n--;
    }
    while(!langerA && n > 0){
        headB = headB.next;
        n--;
    }
    
    //两个链表一起移动直到到达终点或者相交
    while(headA != headB){
        headA = headA.next;
        headB = headB.next;
    }
    return headA;
}

另一种思路

假设 A 长度 length(A)，B 长度 length(B)，A 相交前的长度为 c，B 相交前的长度为 d，那么：length(A) - c = length(B) - d，整理得到：length(A) + d = length(B) + c，这个式子说明我们经过遍历和交换后步伐将会一致，具体可举例模拟，非常巧妙。 当步伐一致后，如果能够遇到相交的第一个节点，则跳出 while，返回 a 指向的相交节点指针；若找不到相交节点，则最终两个指针均走向末尾 null，此时也会跳出 while，并且返回 null。

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    ListNode tempA = headA;
    ListNode tempB = headB;
    while (tempA != tempB) {
        tempA = tempA == null ? headB : tempA.next;
        tempB = tempB == null ? headA : tempB.next;
    }
    return tempA;
}