题目
代码
求两个链表的相交部分（共同部分），很容易想到的是用集合（指针也能作为Map的key）：
1
2
3
4
5
6
7
8
9
10
11
12
13
| func getIntersectionNode(headA, headB *ListNode) *ListNode {
set := make(map[*ListNode]bool)
for p := headA; p != nil; p = p.Next {
set[p] = true
}
for p := headB; p != nil; p = p.Next {
if _, ok := set[p]; ok {
return p
}
}
return nil
}
|
这种方法有线性级别的时间和空间复杂度。
我想到一种精彩的譬喻，可以把两个链表看做是两个赛道，这两个赛道长度不同但终点却在同一处。
位于两个赛道上的两个速度相同的选手同时出发，因为赛道长度不同，到达终点的时刻必然不同，但两条赛道的长度和却是一样的（A+B=B+A）。
如果让到达终点的选手立即再去以相同的速度跑另一个赛道，两个选手必能同时到达终点：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| func getIntersectionNode(headA, headB *ListNode) *ListNode {
pa, pb := headA, headB
for pa != pb {
if pa != nil {
pa = pa.Next
} else {
pa = headB
}
if pb != nil {
pb = pb.Next
} else {
pb = headA
}
}
return pa
}
|
上面的方法拥有线性级别的时间复杂度和常数级别的空间复杂度。
此前还想到这种解法，复杂度都差不多，因为“本质”都一样，但我很难描述这种“本质”。。T—T
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
| func getIntersectionNode(headA, headB *ListNode) *ListNode {
lenA := length(headA)
lenB := length(headB)
for {
if lenA == 0 || lenB == 0 {
return nil
}
if headA == headB {
return headA
} else {
if lenA > lenB {
headA = headA.Next
lenA--
} else if lenA == lenB {
headA = headA.Next
lenA--
headB = headB.Next
lenB--
} else {
headB = headB.Next
lenB--
}
}
}
}
func length(head *ListNode) (ans int) {
for p := head; p != nil; p = p.Next {
ans++
}
return
}
|