【链表, 哈希表, 双指针】相交链表

题目

160. 相交链表

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

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

题目数据 保证 整个链式结构中不存在环。

注意，函数返回结果后，链表必须 保持其原始结构 。

自定义评测：

评测系统 的输入如下（你设计的程序不适用此输入）：

intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0
listA - 第一个链表
listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数
skipB - 在 listB 中（从头节点开始）跳到交叉节点的节点数

评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB 传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 **视作正确答案 **。

示例 1：

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

示例 2：

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'
解释：相交节点的值为 2 （注意，如果两个链表相交则不能为 0）。
从各自的表头开始算起，链表 A 为 [1,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 。

提示：

listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 10^4
1 <= Node.val <= 10^5
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

解题

方法一：哈希表

思路

遍历第一个链表每个节点全部放入集合中，遍历第二个链表，如果集合中包含第二个链表的节点，说明两链表相交，返回该重复节点则为相交节点。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> hash = new HashSet<>();
        while(headA != null) {
            hash.add(headA);
            headA = headA.next;
        }
        while(headB != null) {
            if (hash.contains(headB)) return headB;
            headB = headB.next;
        }
        return null;
    }
}

方法二：双指针

思路1：两链表交叉拼接

维护两个指针(p1、p2)分别指向 headA 和 headB，如何让 p1 和 p2 同时到达相交节点就成了解决这题的关键。

所以，我们可以让 p1 遍历完链表 A 之后开始遍历链表 B，让 p2 遍历完链表 B 之后开始遍历链表 A，这样相当于「逻辑上」两条链表接在了一起。

如果这样进行拼接，就可以让 p1 和 p2 同时同时到达相交节点 c1：

这时如果 p1 和 p2 相等就能得出结论：

如果 p1 == p2 != null 那么两链表相交与 p1 的位置。
如果 p1 == p2 == null 那么两链表不相交(本该相交的位置为空)。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode ptr1 = headA, ptr2 = headB;
        while (ptr1 != ptr2) {
            if (ptr1 != null) ptr1 = ptr1.next;
            else ptr1 = headB;
            if (ptr2 != null) ptr2 = ptr2.next;
            else ptr2 = headA;
        }
        return ptr1;
    }
}

思路2：两链表头尾相连

当我们把两链表头尾相连：

会发现，这题变成了：【链表, 哈希表, 双指针】环形链表 II

我们要求的节点 c1 变成了环形链表中环开始的位置，求法详见上面环形链表II的解题。

注意：题目要求函数返回结果后，链表必须保持其原始结构，所以拼接的链表在返回前一定要还原。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode node = headA;
        while (node.next != null) node = node.next;
        ListNode tailA = node;
        tailA.next = headB;
        ListNode slow = headA, fast = headA;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                slow = headA;
                while(slow != fast) {
                    slow = slow.next;
                    fast = fast.next;
                }
                tailA.next = null;
                return slow;
            }
        }
        tailA.next = null;
        return null;
    }
}

思路3：提前计算链表长度

既然需要保证两个指针同时到达相交节点，而如果后面有相交部分那么相交节点到两个链表结尾的长度应该时固定的，也就是说我们只需要保证两个指针相对于其链表结尾的距离相同即可。
于是我们可以直接提前计算两链表长度，把较长链表从前面砍到和另一个链表相同的长度再开始扫描两个链表即可。

代码

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode p1 = headA, p2 = headB;
        int lenA = 0, lenB = 0;
        while (p1 != null) {
            p1 = p1.next;
            ++lenA;
        }
        while (p2 != null) {
            p2 = p2.next;
            ++lenB;
        }
        p1 = headA;
        p2 = headB;
        while (lenA > lenB) {
            p1 = p1.next;
            --lenA;
        }
        while (lenA < lenB) {
            p2 = p2.next;
            --lenB;
        }
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p1;
    }
}

目录CONTENT