Intersection of two linked list
获得两条链表的连接点
my solution (36ms, 100%)
(虽然效率看起来是最好的, 但是其实比起最好的算法要差不少)
核心难点在于两条链表的长度不一定相等, 这样就不能遍历节点用等于的形式来判断
那么拿到两条链表的长度, 让较长的链表前进若干次, 以达到长度相等的情形, 那么就可以遍历了
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
| class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int deep_A = 0, deep_B = 0;
ListNode *temp_head = headA;
while (temp_head) {
temp_head = temp_head->next;
++deep_A;
}
temp_head = headB;
while (temp_head) {
temp_head = temp_head->next;
++deep_B;
}
int distance = abs(deep_A - deep_B);
if (deep_A > deep_B) {
while (distance) {
headA = headA->next;
--distance;
}
} else {
while (distance) {
headB = headB->next;
--distance;
}
}
while (headA && headB && headA != headB) {
headA = headA->next;
headB = headB->next;
}
return headA;
}
};
|
代码如下, 会产生 3 次遍历, 两次完整的遍历 O(3n) => O(n)
the best solution
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *p = headA;
ListNode *q = headB;
while (p != q) {
p = (p ? p->next: headB);
q = (q ? q->next: headA);
}
return p;
}
};
|
原来还可以这么做!!!
算法的核心思想在于, A + B = B + A
假设有两条链表, 长度不等
0 0 0 2 1 1 // A
0 0 2 1 1 // B
其中将他们的链接点标为 2
那么有以下组合链表
0 0 0 2 1 1 0 0 2 1 1 // A + B
0 0 2 1 1 0 0 0 2 1 1 // B + A
他们如果有链接点, 那么在第二次循环时必然相等
我是用求深度差来解决这个问题, 这个算法更加巧妙地用组合链表的形式规避了这个深度差