一、题目描述
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：
在节点 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; } }
