Intersection: Given two (singly) linked lists, determine if the two lists intersect. Return the intersecting node. Note that the intersection is defined based on reference, not value.That is, if the kth node of the first linked list is the exact same node (by reference) as the jth node of the second linked list, then they are intersecting.
解法1
判断两个链表是否交叉简单，只需把两链表走到底，看最后一个node是否是同一个就行了。因为两链一旦交叉那肯定殊途同归。
1
2
3
4
5
|
A -> B -> C
\
-> D -> E -> F
/
X -> Y
|
那么怎么知道交叉点是哪个node？
我们做一个Set<Node>记录之前出现过的node，分别遍历两个链表，当发现某个node出现了两次，那么它就是交叉点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public Node intersect(Node a, Node b) {
Set<Node> nodes = new HashSet<>();
while (a != null) {
nodes.add(a);
a = a.next;
}
while (b != null) {
if (nodes.contains(b)) {
return b;
}
b = b.next;
}
return null;
}
|
解法2
解法1的空间复杂度比较大，看看能不能O(1)。
如果两个链表的长度一样，那么我们可以同时从两个链表的头部开始遍历，然后对比一下，就能够找到交叉点。
如果不一样呢？那我们是否可以先让长的那个指针先走几步，然后再一起走（齐头并进），就能够找到交叉点了。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
public Node intersect(Node a, Node b) {
int lenA = length(a);
int lenB = length(b);
if (lenA > lenB) {
a = skip(a, lenA - lenB);
}
if (lenB > lenA) {
b = skip(b, lenB - lenA);
}
while (a != null) {
if (a == b) {
return a;
}
a = a.next;
b = b.next;
}
return null;
}
int length(Node a) {
int len = 0;
while (a != null) {
len++;
a = a.next;
}
return len;
}
Node skip(Node a, int step) {
for (int i = 0; i < step; i++) {
a = a.next;
}
return a;
}
|
评论