【LeetCode 160】算法：相交链表 —— 双指针法和数学法

题目：给你两个单链表的头节点 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 代码：

1. public class Solution {
2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
3.         ListNode pointerA = headA;
4.         ListNode pointerB = headB;
6.         while (pointerA != pointerB) {
7.             pointerA = (pointerA == null) ? headB : pointerA.next;
8.             pointerB = (pointerB == null) ? headA : pointerB.next;
9.         }
11.         return pointerA; // 当两个指针相遇时，返回相遇的节点
12.     }
13. }

复制代码

二、数学法
算法步骤：

• 计算长度：分别计算两个链表的长度。
  
• 找齐头尾：让较长的链表先移动，使其头指针与较短的链表头指针相距相同的步数。
  
• 同时遍历：从两个链表的头指针开始，同时遍历两个链表，如果两个链表相交，那么这两个指针最终会在相交点相遇；如果不相交，那么两个指针最终都会到达 null。
  

Java 代码：

1. public class Solution {
2.     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
3.         if (headA == null || headB == null) {
4.             return null;
5.         }
7.         // 计算两个链表的长度
8.         int lenA = 0, lenB = 0;
9.         ListNode tmpA = headA, tmpB = headB;
10.         while (tmpA != null) {
11.             lenA++;
12.             tmpA = tmpA.next;
13.         }
14.         while (tmpB != null) {
15.             lenB++;
16.             tmpB = tmpB.next;
17.         }
19.         // 让较长的链表先移动，使其头指针与较短的链表头指针相距相同的步数
20.         while (lenA > lenB) {
21.             headA = headA.next;
22.             lenA--;
23.         }
24.         while (lenB > lenA) {
25.             headB = headB.next;
26.             lenB--;
27.         }
29.         // 从两个链表的头指针开始，同时遍历两个链表
30.         while (headA != null && headA != headB) {
31.             headA = headA.next;
32.             headB = headB.next;
33.         }
35.         // 如果两个链表相交，返回相交的节点；否则返回null
36.         return headA;
37.     }
38. }

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

用心讨论，共获提升！