剑指 Offer 52. 两个链表的第一个公共节点

题目

输入：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 个节点。

输入：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 个节点。

输入：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。

解题方法一

  /**
     * 首先获取两条链表长度，计算出差值，并让较长的先移动多出的几个节点，使得两指针指向的后续节点长度相等，
     * 然后同时向后遍历，如果指向同一节点，返回！
     *
     * 力扣跑起来超出时间限制！！
     * 代码没有测试 应该没有问题
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode0(ListNode headA, ListNode headB) {
        // 处理边界条件
        if (headA == null || headB == null){
            return null;
        }
        ListNode pA = headA, pB = headB;
        // 获取两条链表的长度
        int lenA = 0;
        int lenB = 0;
        while (pA != null){
            lenA++;
            pA = pA.next;
        }
        while (pB != null){
            lenB++;
            pA = pB.next;
        }
        // 比较链表长度 让较长的移动多出的几个节点
        int diff = lenA - lenB;
        if (diff >= 0){
            while (diff-- != 0){
                headA = headA.next;
            }
        }else {
            while (diff++ != 0){
                headB = headB.next;
            }
        }
        // 此时指针指向的链表以后长度相等
        // 如果知道相同节点直接返回
        while (headA != null && headB != null && headA != headB){
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }

解题方法二

/**
     * 使用哈希集合HashSet
     * HashSet 基于 HashMap 来实现的，是一个不允许有重复元素的集合。
     *
     * 时间复杂度：O(m+n)，其中 m 和 n 是分别是链表 headA 和 headB 的长度。需要遍历两个链表各一次。
     * 空间复杂度：O(m)，其中 m 是链表 headA 的长度。需要使用哈希集合存储链表 headA 中的全部节点。
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
        // 处理边界条件
        if (headA == null || headB == null){
            return null;
        }
        Set<ListNode> visited = new HashSet<ListNode>();
        // 将链表A全部节点放入hashSet
        ListNode temp = headA;
        while (temp != null) {
            visited.add(temp);
            temp = temp.next;
        }
        // 遍历另一个链表B
        temp = headB;
        while (temp != null) {
            // 因为是一个hashSet不允许有重复元素的集合，如果遇到相同节点那就是重合节点
            if (visited.contains(temp)) {
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }

解题方法三

双指针思路和算法

使用双指针的方法，可以将空间复杂度降至 O(1)。

只有当链表 headA 和headB 都不为空时，两个链表才可能相交。因此首先判断链表headA 和 headB 是否为空，如果其中至少有一个链表为空，则两个链表一定不相交，返回 null。

当链表 headA 和 headB 都不为空时，创建两个指针pA 和pB，初始时分别指向两个链表的头节点 headA 和 headB，然后将两个指针依次遍历两个链表的每个节点。具体做法如下：

每步操作需要同时更新指针 pA 和 pB。

如果指针 pA 不为空，则将指针pA 移到下一个节点；如果指针pB 不为空，则将指针pB 移到下一个节点。

如果指针 pA 为空，则将指针 pA 移到链表 headB 的头节点；如果指针pB 为空，则将指针 pB 移到链表 headA 的头节点。

当指针pA 和pB 指向同一个节点或者都为空时，返回它们指向的节点或者null。

 /**
     * 使用双指针移动
     *
     * 时间复杂度：O(m+n)，其中 m 和 n是分别是链表 headA 和 headB 的长度。
     * 两个指针同时遍历两个链表，每个指针遍历两个链表各一次。
     * 空间复杂度：O(1)。
     *
     * 其实就是让两个指针把两条链表都遍历一遍，只不过起点不同，但是因为总长度一样，所以当第二次遍历到相同节点时，
     * 两指针同时到达！
     *
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
        // 处理边界条件
        if (headA == null || headB == null){
            return null;
        }
        // 使用双指针移动
        ListNode pa = headA, pb = headB;
        while (pa != pb){
            pa = pa == null ? headB : pa.next;
            pb = pb == null ? headA : pb.next;
        }
        return pb;
    }

微信关注

WeChat