160. 相交链表
查看题目简单
链表
图
高频
解法一：哈希表优化
时间复杂度：O(m + n) | 空间复杂度：O(m) | 推荐使用
动画演示
准备就绪 - 输入两个链表的值和相交点位置，然后点击开始
代码实现
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
Set<ListNode> visited = new HashSet<ListNode>();
ListNode temp = headA;
while (temp != null) {
visited.add(temp);
temp = temp.next;
}
temp = headB;
while (temp != null) {
if (visited.contains(temp)) {
return temp;
}
temp = temp.next;
}
return null;
}
}
时间复杂度：O(m + n)
空间复杂度：O(m)
哈希表法：
1. 遍历链表A，将每个节点存入哈希表
2. 遍历链表B，检查每个节点是否在哈希表中
3. 第一个在哈希表中出现的节点即为相交节点
时间复杂度：O(m + n)，其中m和n分别为两个链表的长度
空间复杂度：O(m)，需要额外的哈希表存储链表A的所有节点
解法二：双指针
时间复杂度：O(m + n) | 空间复杂度：O(1)
动画演示
准备就绪 - 输入两个链表的值和相交点位置，然后点击开始
代码实现
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;
}
}
时间复杂度：O(m + n)
空间复杂度：O(1)
双指针法：
1. 初始化两个指针pA和pB，分别指向链表A和链表B的头节点
2. 同时遍历两个链表，当pA到达链表A末尾时，将其重定向到链表B的头节点
3. 当pB到达链表B末尾时，将其重定向到链表A的头节点
4. 继续遍历，直到pA和pB相遇，相遇点即为相交节点
时间复杂度：O(m + n)，其中m和n分别为两个链表的长度
空间复杂度：O(1)，只需要常数级别的额外空间