给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。

双链表图解：

一图胜千言，看图你就明白了

空间复杂度 O(1)O(1)O(1) 时间复杂度为 O(n)O(n)O(n)

这里使用图解的方式，解释比较巧妙的一种实现。

根据题目意思 如果两个链表相交，那么相交点之后的长度是相同的

我们需要做的事情是，让两个链表从同距离末尾同等距离的位置开始遍历。这个位置只能是较短链表的头结点位置。 为此，我们必须消除两个链表的长度差

指针 pA 指向 A 链表，指针 pB 指向 B 链表，依次往后遍历
如果 pA 到了末尾，则 pA = headB 继续遍历
如果 pB 到了末尾，则 pB = headA 继续遍历
比较长的链表指针指向较短链表head时，长度差就消除了
如此，只需要将最短链表遍历两次即可找到位置
听着可能有点绕，看图最直观，链表的题目最适合看图了

package TOP11_20;import java.util.HashSet;
import java.util.Set;// 相交链表
/*
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。图示两个链表在节点 c1 开始相交：题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。*/
public class Top20 {public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {// 用hash表 空间复杂度会是o(m) 时间复杂度是o(n)if(headA == null || headB == null){return null;}Set<ListNode> sets = new HashSet<>();ListNode temp = headA;while (temp!=null){sets.add(temp);temp=temp.next;}temp = headB;while (temp!=null){if(sets.contains(temp)){return temp;}temp = temp.next;}return null;}public class ListNode {int val;ListNode next;ListNode(int x) {val = x;next = null;}}//双指针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 pA;}
}

harryptter / LeetcodeTop100 · GitCode