牛客网新出了一个算法速刷 TOP101 题单，按照标签进行分类刷题，涵盖了链表、二分查找、排序、二叉树、堆、栈、队列、哈希、递归、回溯算法、动态规划、字符串、双指针、贪心算法、模拟算法等多个高频知识考点，准备校招、临时突击算法面试的同学可以根据这份题单进行系统的刷题。
题单地址：https://www.nowcoder.com/link/pc_kol_wsx
一、题目描述
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
二、题目解析
这道题目如果模拟一下很容易发现一个规律：无论 A、B 两个链表是否有相交点，最终都会指向一个相同的节点，要么是它们的公共尾部，要么是 NULL。
让指针 pointA 和 pointB 分别指向链表 A 和链表 B 的头结点，之后两个指针分别以步幅为 1 的速度向链表的尾部遍历。
- 当指针
pointA遍历到链表 A 的尾节点时，此时指针pointA走了 a 个节点，将指针pointA指向链表 B 的头部，继续向后遍历，直至走到c1，此时指针pointA总共走了a + ( b - c )步。 - 当指针
pointB遍历到链表 B 的尾节点时，此时指针pointB走了 b 个节点，将指针pointB指向链表 A 的头部，继续向后遍历，直至走到c1，此时指针pointB总共走了b + ( a - c )步。
根据数学知识，a + ( b - c ) = b + ( a - c ) ，如果 c > 0，表明两链表有公共尾部， c1 存在，两两链表同时到达 c1；如果 c = 0，表明两链表没有公共尾部，指针 pointA 和 pointB 都指向 NULL。
三、参考代码
// 本题文字版详解请访问下方网站
// https://www.algomooc.com
// 作者：程序员吴师兄
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 边界判断
if (headA == null || headB == null) return null;
// 设置一个指针 pointA，指向链表 A 的头节点
ListNode pointA = headA;
// 设置一个指针 pointB，指向链表 B 的头节点
ListNode pointB = headB;
// 指针 pointA 和 指针 pointB 不断向后遍历，直到找到相交点
// 不用担心会跳不出这个循环，实际上在链表 headA 长度和链表 headB 长度的最小公倍数的情况下
// pointA 和 pointB 都会同时指向 null
// 比如 headA 的长度是 7，headB 的长度是 11，这两个链表不相交
// 那么 pointA 移动了 7 * 11 = 77 次之后，会指向 null
// pointB 移动了 7 * 11 = 77 次之后，也指向 null
// 这个时候就跳出了循环
while (pointA != pointB) {
// 指针 pointA 一开始在链表 A 上遍历，当走到链表 A 的尾部即 null 时，跳转到链表 B 上
if( pointA == null){
// 指针 pointA 跳转到链表 B 上
pointA = headB;
}else{
// 否则的话 pointA 不断的向后移动
pointA = pointA.next;
}
// 指针 pointB 一开始在链表 B 上遍历，当走到链表 B 的尾部即 null 时，跳转到链表 A 上
if( pointB == null){
// 指针 pointA 跳转到链表 B 上
pointB = headA;
}else{
// 否则的话 pointB 不断的向后移动
pointB = pointB.next;
}
}
// 1、此时，pointA 和 pointB 指向那个相交的节点，返回任意一个均可
// 2、此时，headA 和 headB 不想交，那么 pointA 和 pointB 均为 null，也返回任意一个均可
return pointA;
}
}
