【链表】相交链表

题目来源：相交链表

解法一：使用哈希表记录其中一个链表出现过的所有结点，之后再遍历另一个链表即可。HashMap和HashSet都可以。

解法二：

假设链表1长度为：m，链表2长度为n，若有相交点，则假设从相交点到链表末尾的长度为b。

则链表1不相交的长度为：m-b，链表2不相交的长度为：n-b。

因为：m + n - b = n + m - b

m + n - b可以理解为：走完m，再走完n - b；

n + m - b可以理解为：走完n，再走完m - b；

当m == n时，只需要走一条链表的长度，就可以找到相交的结点 或者 不相交；

当m != n时，才需要走完本身的链表再走下一条链表。

class Solution {
    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 ? headB : p1.next;
          p2 = p2 == null ? headA : p2.next;
        }
        
        return p1;
    }
}

执行用时：1 ms, 在所有 Java 提交中击败了99.98%的用户

内存消耗：41.3 MB, 在所有 Java 提交中击败了43.39%的用户

通过测试用例：39 / 39

复杂度分析

        时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 headA 和 headB 的长度。两个指针同时遍历两个链表，每个指针遍历两个链表各一次。

        空间复杂度：O(1)。