实现两个有序链表的合并

思路一:非递归
两个链表是排序过的,所以我们只需要同时遍历两个链表,比较链表元素的大小,将小的连接到新的链
表中即可。最后,可能有一个链表会先遍历完,此时,我们直接将另一个链表连接到新链表的最后即可。

struct listnode* merge_list(struct listnode* H1,struct listnode* H2)
{
    struct listnode* H;
    if(H1==NULL)
        return H2;
    if(H2==NULL)
        return H1;
    if((H=(struct listnode*)malloc(sizeof(struct listnode)))==NULL)
    {  
      printf("malloc filed\n");
      return NULL;
    }
    struct listnode* pre=H;
    while(H1 && H2)
    {
        if(H1->data <= H2->data)
        {
            pre->next=H1->data;
            H1=H1->next;
        }else{
             pre->next=H2->data;
             H2=H2->next;
        }
        pre=pre->next;
    }
    pre->next=(NULL == H1 ? H2:H1);
    return H->next;
}

思路二:递归
在两表都不为空的情况下,如果一个表当前data更小,把该表的next修改为(next)与(另一个表)中更小者。

struct listnode* merge_list(struct listnode* H1,struct listnode* H2)
{
    if(H1==NULL)
        return H2;
    if(H2==NULL)
        return H1;
    if(H1->data < H2->data){
        H1-next=merge_list(H1->next,H2);
        return H1;
    }else{
        H2-next=merge_list(H1,H2-next);     
        return H2;
    }
}
全部评论

相关推荐

有没有佬投这个呀,怎么样呀求问
投递中科院空天信息创新研究院等公司10个岗位
点赞 评论 收藏
分享
07-19 13:28
长沙学院 Java
程序员小白条:你有面试就有希望,没面试自然就没希望,到时候就知道了,你问别人也没啥用处的
点赞 评论 收藏
分享
评论
点赞
1
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务