一、题目描述

输入两个链表，找出它们的第一个公共节点。

如下面的两个链表：

在节点 c1 开始相交。

示例 1：

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

示例 2：

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

示例 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。

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

二、思路讲解

最简单的方法是想到HashSet。将一个链表A的节点全部放入集合中，然后遍历另一个链表B，若B中某个节点存在于集合中，说明后面的结构是A、B共同的子结构。

三、Java代码实现

/**
 * 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 temp = headA;
        Set<ListNode> set = new HashSet<>();
        while(temp != null){
            set.add(temp);
            temp = temp.next;
        }

        temp = headB;
        while(temp!=null){
            if(set.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }
}

四、时空复杂度分析

时间复杂度： O(M+N) 需要遍历两个链表

空间复杂度： O(N) 需要存储一个链表

五、代码优化

1、使用双指针空间复杂度降为O(1)

由于两个链表不一样长，那么我们用两个指针分别指向链表的头，较长的那个指针先走，等走到一样长的位置时，再一起走，如果两个指针所指的节点相同，就返回。

如果没有公共部分，也成立，这种情况下走到链表最后的null的时候，返回null。

/**
 * 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 pa = headA;
        ListNode pb = headB;
        int len_a = 0;  //链表A长度
        int len_b = 0;  //链表B长度
        //计算链表A长度
        while(pa != null){
            len_a++;
            pa = pa.next;
        }
        //计算链表B长度
        while(pb != null){
            len_b++;
            pb = pb.next;
        }

        pa = headA;
        pb = headB;
        //长的先跑
        if(len_a > len_b){
            for(int i=0; i<len_a - len_b; i++){
                pa = pa.next;
            }
        } else {
            for(int i=0; i<len_b - len_a; i++){
                pb = pb.next;
            }
        }

        //一起跑
        while(pa != pb){
            pa = pa.next;
            pb = pb.next;
        }
        return pa;
    }
}

2、更优雅的双指针

还是让两个指针分别指向两个链表，假设指针pa指向headA，指针pb指向headB。当pa遍历玩A链表之后，去遍历B链表；当pb遍历完B链表之后，去遍历A链表。当两指针相遇时，即为公共部分的第一个节点。

如何证明？

假设A链表长度为a，B链表长度为b，公共部分长度为c。那么，pa遍历完A链表，走的长度为a，此时它去遍历B链表，走到公共节点处，一共需走a+(b-c)；pb遍历完B链表，走的长度为b，此时它去遍历A链表，走到公共节点处，一共需走b+(a-c)。两个指针所走的长度恰好相等。所以，当两指针第一次相遇，所处的节点即是所求。

再看看如果没有公共节点，是否成立。

没有公共节点，则c=0。表示pa遍历完A,B；pb遍历完B,A，最后都为null，此时跳出循环，返回null。成立。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = (A!=null) ? A.next : headB;
            B = (B!=null) ? B.next : headA;
        }
        return A;
    }
}

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/125053.html