您当前的位置:首页 > 计算机 > 编程开发 > C语言

求两个递增链表A和B的交集,并将结果放在链表A中

时间:01-03来源:作者:点击数:

问题描述:

已知两个链表A和B分别表示两个集合,其元素递增排列。编制函数,求A与B 的交集,并存放于A链表中。

问题解答:

算法思想:用归并的思想,设置两个工作指针pa和pb,对两个链表进行归并扫描,只有同时出现在两集合中的元素才链接到结果表中且仅保留一个,其他的结点全部释放。当一个链表遍历完毕后,释放另一个表中剩下的全部结点。

LinkList Union(LinkList &la,LinkList &lb) {
    pa=la->next;  //设工作指针分别为pa和pb
    pb=lb->next;
    pc=la;  //结果表中当前合并结点的前驱指针
    while(pa&&pb){
        if(pa->data==pb->data) {  //交集并入结果表中
            pc->next=pa;    //A中结点链接到结果表
            pc=pa;
            pa=pa->next;
            u=pb;  //B中结点释放
            pb=pb->next;
            free(u);
        }
        else if (pa->data<pb->data) { //若A中当前结点值小于B中当前结点值
            u=pa;
            pa=pa->next;  //后移指针
            free(u) ; //释放A中当前结点
        }else{  //若B中当前结点值小于A中当前结点值
            u=pb;
            pb=pb->next;  //后移指针
            free (u) ;  //释放B中当前结点
        }
    }  //while 结束
    while(pa){    //B已遍历完,A未完
        u=pa;
        pa=pa->next;
        free (u) ;  //释放A中剩余结点
    }
    while(pb){  //A已遍历完,B未完
        u=pb;
        pb=pb->next;
        free(u) ; //释放B中剩余结点
    }
    pc->next=NULL;    //置结果链表尾指针为NULL
    free (lb) ;    //释放B表的头结点
    return la;
}

链表归并类型的题在各学校历年真题中出现的频率很高,故应扎实掌握此类问题的思想。该算法的时间复杂度为O(len1+len2),空间复杂度为O(1)。

方便获取更多学习、工作、生活信息请关注本站微信公众号城东书院 微信服务号城东书院 微信订阅号
推荐内容
相关内容
栏目更新
栏目热门