力扣面试题02.07.链表相交

题目链接：面试题 02.07. 链表相交 - 力扣（LeetCode）

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

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

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

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

示例 1：

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '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
输出：Intersected at '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 。

提示：

• listA 中节点数目为 m

• listB 中节点数目为 n

• 0 <= m, n <= 3 * 104

• 1 <= Node.val <= 105

• 0 <= skipA <= m

• 0 <= skipB <= n

• 如果 listA 和 listB 没有交点，intersectVal 为 0

• 如果 listA 和 listB 有交点，intersectVal == listA[skipA + 1] == listB[skipB + 1]

解法一：哈希集合

思路：

遍历链表A，将链表A中的所有节点添加到HashSet集合中，然后遍历链表B，对于遍历到的每个节点，判断该节点是否在哈希集合中：

• 如果当前节点不在哈希集合中，则继续遍历下一个节点；

• 如果当前节点在哈希集合中，则后面的节点都在哈希集合中，返回该节点。

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        Set<ListNode> m=new HashSet<ListNode>();
        ListNode currA=headA;
        ListNode currB=headB;
        while(currA!=null){
            m.add(currA);
            currA=currA.next;
        }
        while(currB!=null){
            if(m.contains(currB)){
                return currB;
            }else{
                currB=currB.next;
            }
        }
        return null;
    }
}

复杂度分析：

时间复杂度：O(n + m)         遍历两条链表

空间复杂度：O(m)         哈希集合

解法二：同步移动

思路：

1.求出两个链表的长度，计算出两个链表长度的差值，移动currA或currB使两者同步。

2.此时我们就可以比较currA和currB是否相同，如果不相同，同时向后移动currA和currB，如果遇到currA == currB，则找到交点并返回该节点。

否则返回空指针。

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode currA=headA;
        ListNode currB=headB;
        int numA=0,numB=0;
        //注意交点不是数值相等，而是指针相等
        while(currA!=null){
            numA++;//链表A的长度
            currA=currA.next;
        }
        while(currB!=null){
            numB++;//链表B的长度
            currB=currB.next;
        }
        currA=headA;
        currB=headB;
        
        int t=0;
        if(numA>numB){
            t=numA-numB;
            while(t!=0){
                currA=currA.next;//currA先走，直到和B同步
                t--;
            }
            //此时currA和currB同步
            while(currA!=null&&currB!=null){
                if(currA==currB){
                    return currA;
                }else{
                    currA=currA.next;
                    currB=currB.next;
                }
            }
        }else{
            t=numB-numA;
            while(t!=0){
                currB=currB.next;//currB先走，直到和A同步
                t--;
            }
            //此时currA和currB同步
            while(currA!=null&&currB!=null){
                if(currA==currB){
                    return currA;
                }else{
                    currA=currA.next;
                    currB=currB.next;
                }
            }
        }
        return null;
    }
}

复杂度分析： 

时间复杂度： O(m+n)        遍历链表A：O（m），遍历链表B：O（n）同步指针：O（t）

空间复杂度：O(1)

解法三：双指针

思路：

使用双指针实现同步遍历

• 当p1遍历完链表A（p1==null）后，让它开始遍历链表B。
• 当p2遍历完链表B（p2==null）后，让它开始遍历链表A。

代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public 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 走一步，如果走到 A 链表末尾，转到 B 链表
            if(p1==null) p1=headB;
            else p1=p1.next;
            // p2 走一步，如果走到 B 链表末尾，转到 A 链表
            if(p2==null) p2=headA;
            else p2=p2.next;
        }
        return p1;
    }
}

复杂度分析：

时间复杂度：O(m + n)         遍历两条链表

空间复杂度：O(1)