目录
题目
160. 相交链表
思路1
- 我们可以将另一端链表虚拟拼接（如果实际改变指针的话会导致死循环）到本段链表后面（null不要省略），两个链表此时时灯等长的。然后两个链表同时从头开始遍历，如果存在相交的结点，那么
p1 != p2就不会成立，因此找到答案，退出循环；如果没有找到答案，最后都会为null，同样跳出循环，得到结果
- 例1（相交）：
- headA={4, 2, 8, 4, 5}，headB={5, 0, 1, 8, 4, 5}，虚拟拼接后为：
- headA={4, 2, 8, 4, 5, null, 5, 0, 1, 8, 4, 5, null}，headB={5, 0, 1, 8, 4, 5, null, 4, 2, 8, 4, 5, null}
- 当索引为9时，结点都是8，此时退出循环，找到答案
- 例2（不相交）：
- headA={1, 2, 3}，headB={4, 3, 2, 1}，虚拟拼接后为：
- headA={1, 2, 3, null, 4, 3, 2, 1, null}，headB={4, 3, 2, 1, null, 1, 2, 3, null}
- 当索引为8时，两个指针都指向null，此时也退出循环，不过返回的时null，即没有找到答案
代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 如果其中一个存在空链表，直接返回null
if (headA == null || headB == null) {
return null;
}
ListNode p1 = headA;
ListNode p2 = headB;
// 当还没相遇时，一直遍历下取，如果两个都没有相遇，最终都为null，那么也会退出循环
while (p1 != p2) {
if (p1 == null) {
p1 = headB;
} else {
p1 = p1.next;
}
if (p2 == null) {
p2 = headA;
} else {
p2 = p2.next;
}
}
return p1;
}
}
复杂度分析
- 时间复杂度：\(O(M+N)\)，其中 M、N 为链表长度
- 空间复杂度：\(O(1)\)
思路2
- 使用哈希表，其中一个链表存到哈希表中，然后遍历另一个链表，将其添加到原来的哈希表中，如果存在，就是找到相交的结点了
代码
import java.util.HashSet;
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
HashSet<ListNode> set = new HashSet<>();
while (headA != null) {
set.add(headA);
headA = headA.next;
}
while (headB != null) {
if (!set.add(headB)) {
return headB;
}
headB = headB.next;
}
return null;
}
}
复杂度分析
- 时间复杂度：\(O(M+N)\)，其中 M、N 为链表的长度
- 空间复杂度：\(O(N)/O(M)\)，其中 M、N 为链表的长度
思路3
- 遍历其中一个链表每一个元素时，都将该元素和另一个链表的每一个元素进行比较，如果相等就相交。时间复杂度比较大。。。
代码
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
while (headA != null) {
ListNode p = headB;
while (p != null) {
if (p == headA) {
return headA;
}
p = p.next;
}
headA = headA.next;
}
return null;
}
}
复杂度分析
- 时间复杂度：\(O(MN)\)，其中 M、N 为链表的长度
- 空间复杂度：\(O(1)\)