文章
57
粉丝
0
获赞
0
访问
6.9k
1. 查找两个单链表的第一个公共节点;head1、head2为两个链表的头指针;返回第一个公共节点的指针,如果没有公共节点则返回NULL
2.
Node* findCommon(Node *head1, Node *head2){
Node* current1 = head1;
Node* current2 = head2;
int len1 = 0, len2 = 0;
// 计算链表1长度
while (current1 != NULL){
len1++;
current1 = current1->next;
}
// 计算链表2长度
while (current2 != NULL){
len2++;
current2 = current2->next;
}
// 重新指向头结点
current1 = head1;
current2 = head2;
// 让较长的链表先走差值步
while (len1 > len2){
current1 = current1->next;
len1--;
}
while(len1 < len2){
current2 = current2->next;
len2--;
}
// 同步向后遍历,直到遇到公共节点或到末尾
while(current1 != NULL && current1 != current2){
current1 = current1->next;
current2 = current2->next;
}
return (current1 == current2)?current1:NULL;
}
3. 时间复杂度为 O(m+n)
评分及理由
(1)得分及理由(满分4分)
得分:4分
理由:学生给出的算法基本设...
登录后发布评论
暂无评论,来抢沙发