题目：相交链表
编写一个程序，找到两个单链表相交的起始节点。
答案：
参考链接：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/solution/xiang-jiao-lian-biao-by-leetcode/
1.暴力法
对链表A中的每一个结点 ai ，遍历整个链表 B 并检查链表 B 中是否存在结点和 ai相同。
时间复杂度 : O(mn)。
空间复杂度 : O(1)。
2.哈希表
遍历链表 A 并将每个结点的地址/引用存储在哈希表中。然后检查链表 B 中的每一个结点 bi是否在哈希表中。若在，则 bi为相交结点。
时间复杂度 : O(m+n)。
空间复杂度 : O(m)或O(n)。
3.双指针法
创建两个指针 pA和pB，分别初始化为链表 A 和 B 的头结点。然后让它们向后逐结点遍历。
当 pA到达链表的尾部时，将它重定位到链表 B 的头结点; 类似的，当 pB到达链表的尾部时，将它重定位到链表 A 的头结点。
若在某一时刻 pA和pB相遇，则 pA/pB为相交结点。
解释：
假设链表A、B长度分别为a、b，假设a-b = c，即a比b长c长度（具体谁比谁长无所谓）。
我们需要消除A、B的长度差c，即两个指针在距尾结点距离都为b（较短链表的长度）时，同时往后遍历，遇到的第一个相等的结点即为相交节点。
那如何消除A、B的长度差呢，两个指针 pA和pB分别从A、B头结点向后遍历，pB走到尾结点以后，从A链表头结点开始走，直到pA走到尾结点到B链表头结点，此时，因为pA走过了长度a，所以pB走过了长度a，即pB走过了长度b + c，即pB现在所在位置与pA齐平，消除了长度差。
如果不相交，则pA和pB走过a+b长度后都会指向null，然后返回null
public class Solution {
public ListNode getIntersectionNode(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;
}
}
4.可以先遍历两个节点获取长度，计算长度差offset，然后让长链表指针提前出发offset个节点，这样长短指针就同步了