先记录,后搜索
题中写了数组长度不会超过2000,所以即使先记录下A,再在遍历B的过程中搜索是否与A中的指针有相同的。不过$O(n^2)$的复杂度,没有问题。然而,以下代码最后的结果是12/13,即倒在了最后一个测试样例上,原因是测试样例的数据长度至少有30000。所以,必须进行优化。
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
ListNode *p[50000] = {0}, *head = headA;
int len_A = 0;
while (head){
p[len_A] = head;
len_A ++;
head = head->next;
}
head = headB;
while (head){
for (int i = 0; i < len_A; i ++){
if (head == p[i]) return head;
}
head = head->next;
}
return head;
}
};
反向搜索
上一个算法之所以要用到两层循环,本质原因是因为从左到右A,B相交点的下标是不同的,所以必须固定一个然后遍历另一个,这样会浪费很多运算。不过可以反过来思考,一旦二者有交叉,那么从右到左的下标是相同的。
因此,我们可以先在一次正向遍历的过程中分别记录下每个链表元素的前向位置,然后从最后一个位置开始像前面反向搜索,搜索的目标就是分叉点,即在当前位置下对应的A中的prev和B中的prev不同。如此,复杂度为$O(n)$,可过第13个测试样例。
class Solution {
public:
ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
ListNode *pa[50000][2] = {0}, *pb[50000][2] = {0}, *prev = 0;
int len_A = 0, len_B = 0;
while (headA){
pa[len_A][0] = headA;
pa[len_A][1] = prev;
len_A ++;
prev = headA;
headA = headA->next;
}
prev = 0;
while (headB){
pb[len_B][0] = headB;
pb[len_B][1] = prev;
len_B ++;
prev = headB;
headB = headB->next;
}
int len = min(len_B, len_A);
for (int i = 0; i < len; i ++){
if (pa[len_A-i-1][0] != pb[len_B-i-1][0]) return 0;
if (pa[len_A-i-1][1] != pb[len_B-i-1][1]) return pa[len_A-i-1][0];
}
}
};