题目：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。题目数据 保证 整个链式结构中不存在环。注意，函数返回结果后，链表必须 保持其原始结构 。
有几种不同的算法思路解决这道算法：
1. 双指针法：
-
使用两个指针分别遍历两个链表，如果两个链表相交，那么这两个指针最终会在相交点相遇；如果两个链表不相交，那么这两个指针最终都会到达各自链表的末尾（即 null）。
-
时间复杂度是 O(m + n)，空间复杂度是 O(1)，其中 m 和 n 分别是两个链表的长度，因为最多遍历每个链表两次。
2. 哈希表法：
-
遍历其中一个链表，将所有节点存储在哈希表中。
-
遍历另一个链表，检查每个节点是否在哈希表中。
-
时间复杂度：O(m + n)，空间复杂度：O(m)，其中 m 和 n 分别是两个链表的长度。
3. 数学法：
-
计算两个链表的长度，然后让较长的链表先移动到与较短的链表长度相同的位置，再同时遍历两个链表。
-
时间复杂度：O(m + n)，空间复杂度：O(1)。
4. 递归法：
-
使用递归遍历两个链表，直到找到相交点或到达链表末尾。
-
时间复杂度：O(m + n)，空间复杂度：O(h)，其中 h 是递归深度。
由于双指针法和数学法不需要使用额外的空间，空间复杂度是O(1)，所以我采用双指针法和数学法解决这道题目，下面给出这两个方法的具体步骤和代码。
一、双指针法
算法步骤：
-
初始化两个指针：分别指向两个链表的头节点 headA 和 headB。
-
遍历链表：同时遍历两个链表，直到两个指针都到达 null。
-
指针重置：如果两个指针都到达了 null，则说明两个链表不相交，返回 null。否则，将两个指针重置到对方的链表头节点。
-
再次遍历：再次同时遍历两个链表，这次如果两个链表相交，两个指针将在相交点相遇；如果不相交，两个指针最终都会到达 null。
-
返回结果：如果两个指针相遇，返回相遇的节点；否则返回 null。
Java 代码：
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {ListNode pointerA = headA;ListNode pointerB = headB;while (pointerA != pointerB) {pointerA = (pointerA == null) ? headB : pointerA.next;pointerB = (pointerB == null) ? headA : pointerB.next;}return pointerA; // 当两个指针相遇时，返回相遇的节点}
}
二、数学法
算法步骤：
-
计算长度：分别计算两个链表的长度。
-
找齐头尾：让较长的链表先移动，使其头指针与较短的链表头指针相距相同的步数。
-
同时遍历：从两个链表的头指针开始，同时遍历两个链表，如果两个链表相交，那么这两个指针最终会在相交点相遇；如果不相交，那么两个指针最终都会到达 null。
Java 代码：
public class Solution {public ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA == null || headB == null) {return null;}// 计算两个链表的长度int lenA = 0, lenB = 0;ListNode tmpA = headA, tmpB = headB;while (tmpA != null) {lenA++;tmpA = tmpA.next;}while (tmpB != null) {lenB++;tmpB = tmpB.next;}// 让较长的链表先移动，使其头指针与较短的链表头指针相距相同的步数while (lenA > lenB) {headA = headA.next;lenA--;}while (lenB > lenA) {headB = headB.next;lenB--;}// 从两个链表的头指针开始，同时遍历两个链表while (headA != null && headA != headB) {headA = headA.next;headB = headB.next;}// 如果两个链表相交，返回相交的节点；否则返回nullreturn headA;}
}