需要注意的是，这里的"相交"是指两个链表在某个节点处合并，之后共享剩余的节点。
这道题的关键在于:如果两个链表相交,它们一定有共同的尾节点。
1.首先遍历两个链表，计算两个链表的长度差，然后找到各自的尾节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
ListNode a = h1, b = h2;
int diff = 0;
while (a.next != null) {
a = a.next;
diff++;
}
while (b.next != null) {
b = b.next;
diff--;
}
if (a != b) {
return null;
}
|
用一个变量diff同时记录长度差。
遍历h1时diff++,遍历h2时diff–,最终diff就是两个链表的长度差。
遍历结束后,如果a != b,说明两个链表的尾节点不同,必然不相交。
2.让较长的链表先走若干步,消除长度差。
1
2
3
4
5
6
7
8
9
10
11
|
if (diff >= 0) {
a = h1; // h1更长
b = h2;
} else {
a = h2; // h2更长
b = h1;
}
diff = Math.abs(diff);
while (diff-- != 0) {
a = a.next; // 长链表先走
}
|
3.两个指针距离各自链表尾部的距离相同,接下来同步前进,第一个相同的节点就是交点。
1
2
3
4
5
|
while (a != b) {
a = a.next;
b = b.next;
}
return a;
|
完整代码
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
33
34
35
36
37
38
39
40
41
42
43
|
public static ListNode getIntersectionNode(ListNode h1,ListNode h2){
if(h1==null||h2==null){
return null;
}
ListNode a = h1,b=h2;
int diff =0 ;
//计算长度差，找到h1的尾节点
while(a.next!=null){
a=a.next;
diff++;
}
//计算长度差，找到h2的尾节点
while(b.next!=null){
b= b.next;
diff--;
}
//尾节点不同，不相交
if(a!=b){
return null;
}
//让a指向较长的链表，b指向较短的链表
if(diff>=0){
a=h1;
b=h2;
}else{
a=h2;
b=h1;
}
//长链表先走diff步
diff=Math.abs(diff);
while(diff--!=0){
a=a.next;
}
//同步前进，找到交点
while(a!=b){
a=a.next;
b=b.next;
}
return a;
}
|