LeetCode160：相交链表

1、要求

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

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

自定义评测：
评测系统 的输入如下（你设计的程序 不适用 此输入）：
intersectVal - 相交的起始节点的值。如果不存在相交节点，这一值为 0 listA - 第一个链表 listB - 第二个链表
skipA - 在 listA 中（从头节点开始）跳到交叉节点的节点数 skipB - 在 listB
中（从头节点开始）跳到交叉节点的节点数 评测系统将根据这些输入创建链式数据结构，并将两个头节点 headA 和 headB
传递给你的程序。如果程序能够正确返回相交节点，那么你的解决方案将被 视作正确答案。

2、示例

输入：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 个节点。 — 请注意相交节点的值不为
1，因为在链表 A 和链表 B 之中值为 1 的节点 (A 中第二个节点和 B 中第三个节点)
是不同的节点。换句话说，它们在内存中指向两个不同的位置，而链表 A 和链表 B 中值为 8 的节点 (A 中第三个节点，B 中第四个节点)
在内存中指向相同的位置。

前置条件，如果在自己的工具中测试时，需要创建ListNode类

public class ListNode {
    public int val;
    public ListNode next;

    public ListNode(int x){
        val=x;
    }
}
1
2
3
4
5
6
7
8

3、题目解析

先解析一下题目的意思吧，如果把题目解析明白了，这个题本身并不难，但由于官方解释的有点懵；
这里的相交的意思是值和位置都得相同。所以类似于=== 和 ==的区别：一个要求值和类型都等；一个只要求值相等就行；
下面的是一个大佬发表的评论，我借鉴来了，当时看完就懂了

pA走过的路径为A链+B链
pB走过的路径为B链+A链
pA和pB走过的长度都相同，都是A链和B链的长度之和，相当于将两条链从尾端对齐，如果相交，则会提前在相交点相遇，如果没有相交点，则会在最后相遇。
pA:1->2->3->4->5->6->null->9->5->6->null
pB:9->5->6->null->1->2->3->4->5->6->null

4、解题思路

方法一：HashSet集合

判断两个链表是否相交，可以使用HashSet进行存储判断；
首先遍历链表A，然后将链表A中的结点加入到哈希集合中，然后遍历链表B，对于遍历到的每个节点，判断是否在哈希集合中：

• 如果当前节点不在哈希，则遍历下一个节点
• 如果当前节点在哈希中，后面的结点都在哈希集合中，即从当前节点开始的所有节点都在两个链表的相交部分，因此在链表B中遍历到的第一个哈希集合中的节点就是两个链表相交的地方，返回该节点；

如果链表B中所有节点都不在哈希集合中，则两个链表都不相交返回null。

public class LeetCode160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //创建HashSet集合
        HashSet<ListNode> listNodes = new HashSet<>();
        //如果链表A不为空，则添加到创建的哈希集合中
        while (headA != null){
            listNodes.add(headA);
            headA = headA.next;
        }
        //遍历链表B,对比哈希集合，如果链表B中的值在哈希集合找不到，则返回null
        while (headB != null){
            if (listNodes.contains(headB)){
                return headB;
            }
            headB = headB.next;
        }
        return null;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

时间复杂度：O(m+n)，两个链表各遍历一次
空间复杂度：O(m)，需要借用哈希集合存储链表A

方法二：双指针

只有当链表 A 和 B 都不为空时，两个链表才可能相交。
首先判断链表 A 和 B 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。
如果两个两个链表都不为空，在进行以下判断：

• 如果指针A不为空时，则指向下一个节点；如果指针B不为空时，则指向下一个节点；
• 如果指针A为null时，则将指针A指向链表B的头节点，然后进行指向B的下一个节点；
• 如果指针B为null时，则将指针B指向链表A的头节点，然后进行指向A的下一个节点；
• 直至A和B指针指向同一个节点或者都为空时，返回A和B指向的节点或者返回null
• 如果能有相交的地方，在相交头一个节点位置，链表A和链表B到达末尾的距离是一样的

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
    //双链表
    if (headA == null || headB == null){
        return null;
    }
    ListNode A = headA,B = headB;
    while (A != B){
        A = A == null ? headB : A.next;
        B = B == null ? headA : B.next;
    }
    return B;
}
1
2
3
4
5
6
7
8
9
10
11
12

时间复杂度O(m+n)，最差的情况是这样
空间复杂度O(1)