【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 代码：
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;
}
// 如果两个链表相交，返回相交的节点；否则返回null
return headA;
}
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 用心讨论，共获提升！
页:
[1]