文章

57

粉丝

0

获赞

0

访问

6.9k

头像
2012年(408)计算机学科专业基础综合试题 - 第42题回答
数据结构
发布于2025年11月18日 20:06
阅读数 46

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分

理由:学生给出的算法基本设...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发