首页 > 试题广场 >

合并两个排序的链表

[编程题]合并两个排序的链表
  • 热度指数：1194357 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。
数据范围： ，
要求：空间复杂度 ，时间复杂度

如输入{1,3,5},{2,4,6}时，合并后的链表为{1,2,3,4,5,6}，所以对应的输出为{1,2,3,4,5,6}，转换过程如下图所示：


或输入{-1,2,4},{1,3,4}时，合并后的链表为{-1,1,2,3,4,4}，所以对应的输出为{-1,1,2,3,4,4}，转换过程如下图所示：

示例1

输入

{1,3,5},{2,4,6}

输出

{1,2,3,4,5,6}
示例2

输入

{},{}

输出

{}
示例3

输入

{-1,2,4},{1,3,4}

输出

{-1,1,2,3,4,4}

说明：本题目包含复杂数据结构ListNode，点此查看相关信息
算法知识视频讲解
查看答案及解析
添加回答
C
迷茫的小章鱼在开会头像 迷茫的小章鱼在开会
struct node* he_sort_list(struct node* head1, struct node* head2) {
    struct node* p = malloc(sizeof(struct node));
    struct node* p1 = head1;
    struct node* p2 = head2;
    struct node* phead = p;
    if (head1 == NULL && head2 == NULL) {
        return phead;
    } else if (head1 == NULL && head2 != NULL) {
        return head2;
    } else if (head2 == NULL && head1 != NULL) {
        return head1;
    }
    while (p1 != NULL && p2 != NULL) {

        if (p1->data < p2->data) {
            p->next = p1;
            p1 = p1->next;
            p = p->next;
            if (p1 == NULL) {
                p->next = p2;

            }

        }

        else {
            p->next = p2;
            p2 = p2->next;
            p = p->next;
            if (p2 == NULL) {
                p->next = p1;

            }
        }

    }
    return phead->next;


}

编辑于 2024-04-07 17:11:31 回复(0)
C
南宫梦凝头像 南宫梦凝 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
#include <stdlib.h>
int Length(struct ListNode* pHead){
    struct ListNode* p;
    int len = 0;
    for(p = pHead;p != NULL;p = p->next){
        len++;
    }
    return len;
}
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code 
    struct ListNode* p1,*p1t,*p2,*p3=NULL;
    p1 = pHead1;
    p2 = pHead2;
    if(pHead1 == NULL){
        return pHead2;
    }else if(pHead2 == NULL || (pHead1 == NULL && pHead2 == NULL)){
        return pHead1;
    }else{
        int len1,len2;
        len1 = Length(p1);
        len2 = Length(p2);
        int* mergeArr = (int*)malloc(sizeof(int)*(len1+len2));
        int i,j;
        p1t = pHead1;
        while(p1t->next != NULL){
            p1t = p1t->next;
        }
        p1t->next = p2;
        for(i = 0;i < len1 + len2;i++){
            mergeArr[i] = p1->val;
            p1 = p1->next;
        }

        //冒泡排序
        int temp = 0;
        for(i = 0;i < len1 + len2 - 1;i++){
            for(j = 0;j < len1 + len2 - i - 1;j++){
                if(mergeArr[j] > mergeArr[j+1]){
                    temp = mergeArr[j];
                    mergeArr[j] = mergeArr[j+1];
                    mergeArr[j+1] = temp;
                }
            }
        }
        
        for(i = 0,p1 = pHead1;i<len1 + len2;i++){
            p1->val = mergeArr[i];
            p1 = p1->next;
        }
        return pHead1;

    }   
}


编辑于 2024-04-01 16:16:45 回复(0)
C
徐文达头像 徐文达 
typedef struct ListNode ListNode;

void ListAdd(ListNode** tail, ListNode* node)
{
    (*tail)->next = node;
    *tail = node;
}

struct ListNode* Merge(ListNode* list1, ListNode* list2) 
{
    //判断是否需要进行排序
    if(!list1)
    {
        return list2;
    }
    if(!list2)
    {
        return list1;
    }

    //创建一个新链表，并初始化head、tail为NULL
    ListNode* head = NULL;
    ListNode* tail = NULL;

    //遍历2个链表，同时进行比较，将val较小的结点连接至新链表中
    while(list1 && list2)
    {
        if(list1->val > list2->val)
        {
            //将list2链接至新链表
            if(head == NULL)
            {
                head = tail = list2;
            }
            else
            {
                ListAdd(&tail, list2);
            }
            list2 = list2->next;
        }
        else
        {
            //将list1链接至新链表
            if(head == NULL)
            {
                head = tail = list1;
            }
            else
            {
                ListAdd(&tail, list1);
            }
            list1 = list1->next;
        }
    }
    //链接剩余结点
    if(!list1)
    {
        //链接list2
        ListAdd(&tail, list2);
    }
    else
    {
        //链接list1
        ListAdd(&tail, list1);
    }

    return head;
}

编辑于 2024-03-30 11:04:21 回复(0)
C
一个优雅的程序猿头像 一个优雅的程序猿 
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    if(pHead1==NULL)
        return pHead2;
    else if(pHead2==NULL)
        return pHead1;

    if(pHead1->val < pHead2->val) {
        pHead1->next = Merge(pHead1->next, pHead2);
        return pHead1;
    }
    else {
        pHead2->next = Merge(pHead1, pHead2->next);
        return pHead2;
    }
}

发表于 2024-03-13 20:26:50 回复(0)
C
想去杭州的高级磨洋工在学习头像 想去杭州的高级磨洋工在学习
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
   struct ListNode* head1=pHead1;
   struct ListNode* head2=pHead2;
   struct ListNode* head=(struct ListNode*)malloc(sizeof(struct ListNode));
   struct ListNode* phead=head;
   while(head1&&head2)
   {
    if((head1->val)<(head2->val))
    {
        struct ListNode* nest=(struct ListNode*)malloc(sizeof(struct ListNode));
        phead->next=nest;
        nest->val=head1->val;
        phead=nest;
        head1=head1->next;
    }
    else
    {
        struct ListNode* nest=(struct ListNode*)malloc(sizeof(struct ListNode));
        phead->next=nest;
        nest->val=head2->val;
        phead=nest;
        head2=head2->next;
    }
   }
   if(head1!=NULL)
   {
    phead->next=head1;
   }
   if(head2!=NULL)
   {
    phead->next=head2;
   }
   return head->next;
}
编辑于 2024-03-03 13:23:33 回复(1)
C
慕林悠头像 慕林悠 
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here

    if ((pHead1 == NULL) || (pHead2 == NULL)) {
       pHead1= pHead1==NULL?pHead2:pHead1;
       return pHead1;
    }
    else {//写复杂了，把p2链表中的节点都加到p1中（p1是两个链表中第一个val最小的链表）
        struct ListNode* p1 = (pHead1->val <= pHead2->val ? pHead1 : pHead2);
        struct ListNode* p2 = (pHead1->val > pHead2->val ? pHead1 : pHead2);
        struct ListNode* p = p1;//p1为主链
        struct ListNode* temp;
        while ((p1 != NULL) && (p2 != NULL)) {
            if (p1->val <= p2->val) {
                temp = p1;
                p1 = p1->next;
            } else {
                temp->next = p2;
                temp = p2;
                p2 = p2->next;
                temp->next = p1;
            }
        }
        if (p1 == NULL) {
            temp->next = p2;
            return p;
        } else return p;
    }
}

发表于 2023-11-25 08:38:54 回复(0)
C
南风先生头像 南风先生
不创建新链表直接合并，指针不断跳转就行了
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2) {
    if (pHead1 == NULL) {
        return pHead2;
    }
    if (pHead2 == NULL) {
        return pHead1;
    }

    struct ListNode* newHead = NULL;
    if (pHead1->val <= pHead2->val) {
        newHead = pHead1;
        pHead1 = pHead1->next;
    } else {
        newHead = pHead2;
        pHead2 = pHead2->next;
    }

    struct ListNode* cur = newHead;

    while (pHead1 != NULL && pHead2 != NULL) {
        if (pHead1->val <= pHead2->val) {
            cur->next = pHead1;
            pHead1 = pHead1->next;
        } else {
            cur->next = pHead2;
            pHead2 = pHead2->next;
        }
        cur = cur->next;
    }

    if (pHead1 != NULL) {
        cur->next = pHead1;
    }
    if (pHead2 != NULL) {
        cur->next = pHead2;
    }

    return newHead;
}
发表于 2023-10-07 10:39:27 回复(0)
C
spy.头像 spy.
c语言菜鸟写的，应该是最基础的解法。 
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode*p = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode*pHead = p;//用pHead把p存起来
    if(pHead1 == NULL&&pHead2 == NULL)
        return pHead1;
    else if(pHead1 == NULL&&pHead2 != NULL)
        return pHead2;
    else if(pHead1 != NULL&&pHead2 == NULL)
        return pHead1;
    while(pHead1!=NULL&&pHead2!=NULL)
    {
        if(pHead1->val<pHead2->val)
        {
            p->next = pHead1;
            p = p->next;
            pHead1 = pHead1->next;
        }
        else 
        {
            p->next = pHead2;
            p = p->next;
            pHead2 = pHead2->next;
        }
    }
    if(pHead1 == NULL)
    {
        p->next = pHead2;
    }
    else if(pHead2 == NULL)
    {
        p->next = pHead1;
    }
    return pHead->next;
}


发表于 2023-09-20 17:46:17 回复(0)
C
无名珠头像 无名珠 
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    struct ListNode* p1 = pHead1; //第1个链表的指针
    struct ListNode* p2 = pHead2; //第1个链表的指针
    struct ListNode* ptemp = (struct ListNode*)malloc(sizeof(struct ListNode)); //创建虚拟的头结点
    struct ListNode* p3 = ptemp;

    //本质：改变两个链表的指针走向
    while (p1!=NULL && p2!=NULL)
    {
        if(p1->val > p2->val)
        {
            p3->next = p2;
            p2 = p2->next;
            p3 = p3->next;
        }
        else 
        {
            p3->next = p1;
            p1 = p1->next;
            p3 = p3->next;
        }
    }

    if(p1==NULL) p3->next = p2; //第1个链表结束了，将p2接在后面
    if(p2==NULL) p3->next = p1; //第2个链表结束了，将p1接在后面

    return ptemp->next;
}

发表于 2023-08-19 19:37:28 回复(0)
C
头发2020头像 头发2020
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
#include <stdlib.h>
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode* ret;
    ret = (struct ListNode*)malloc(sizeof(struct ListNode));
    ret->next = NULL;
    struct ListNode* last=ret;
    struct ListNode* t;
   
    while (pHead1 && pHead2) {
        t = (struct ListNode*)malloc(sizeof(struct ListNode));
        if (pHead1->val < pHead2->val){
            t->val = pHead1->val;
            t->next = NULL;
            last->next = t;
            last = t;
            pHead1 = pHead1->next;
        } else {
            t->val = pHead2->val;
            t->next = NULL;
            last->next = t;
            last = t;
            pHead2 = pHead2->next;
        }
    }

    if (pHead2) {last->next = pHead2;}
    if (pHead1) {last->next = pHead1;}
    return ret->next;
}
发表于 2023-08-01 22:46:29 回复(1)
C
海涛的转不动的脑子很想转头像 海涛的转不动的脑子很想转
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2) {
    // write code here
    struct ListNode* L1 = pHead1, * L2 = pHead2;
    struct ListNode* h = (struct ListNode*)malloc(sizeof(struct ListNode*));
    struct ListNode* last = h;
    struct ListNode* s;
    while (L1 != NULL || L2 != NULL)
    {
        if (L1 == NULL)
        {
            while (L2)
            {
                s = (struct ListNode*)malloc(sizeof(struct ListNode));
                s->val = L2->val;
                s->next = NULL;
                last->next = s;
                last = s;
                L2 = L2->next;
            }
        }
        if (L2 == NULL)
        {
            while (L1)
            {
                s = (struct ListNode*)malloc(sizeof(struct ListNode));
                s->val = L1->val;
                s->next = NULL;
                last->next = s;
                last = s;
                L1 = L1->next;
            }
        }
        else
        {
            s = (struct ListNode*)malloc(sizeof(struct ListNode));
            if (L1->val < L2->val)
            {
                s->val = L1->val;
                s->next = NULL;
                last->next = s;
                last = s;
                L1 = L1->next;
            }
            else
            {
                s->val = L2->val;
                s->next = NULL;
                last->next = s;
                last = s;
                L2 = L2->next;
            }
        }
    }
    return h->next;
}
发表于 2023-07-28 22:29:23 回复(0)
C
吾辈长歌头像 吾辈长歌
我觉得我这个应该是最通俗易懂的了吧，虽然代码长 
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) 
{
    if(pHead1==NULL && pHead2==NULL)
        return NULL;
    if(pHead1==NULL && pHead2!=NULL)
        return pHead2;
    if(pHead1!=NULL && pHead2==NULL)
        return pHead1;

    struct ListNode *dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *cur = dummy;
    struct ListNode *p = pHead1;
    struct ListNode *q = pHead2;

    while(p || q) 
    {
        if(p==NULL)
        {
            cur->next = q;
            return dummy->next;
        }
        if(q==NULL)
        {
            cur->next = p;
            return dummy->next;
        }

        if(p->val<q->val)
        {
            cur->next = p;
            cur = cur->next;
            p = p->next;
        }
        else
        {
            cur->next = q;
            cur = cur->next;
            q = q->next;
        }
    }
    return dummy->next;
}

发表于 2023-04-13 00:47:04 回复(0)
C
offer过来自己动头像 offer过来自己动 
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
#include <stdio.h>
#include <stdlib.h>
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2) {
    if (pHead1 == NULL) return pHead2;
    if (pHead2 == NULL) return pHead1;

    struct ListNode* phead = (struct ListNode *)malloc(sizeof(struct ListNode)); //用来合成新的链表，遍历使用
    struct ListNode* head = phead; // 记住头指针
    while (pHead1 && pHead2)
    {
        if (pHead1->val < pHead2->val)
        {
            phead->next = pHead1;
            pHead1 = pHead1->next;
        }
        else
        {
            phead->next = pHead2;
            pHead2 = pHead2->next;
        }
        phead = phead->next;
    }

    if (pHead1 == NULL) phead->next = pHead2;
    if (pHead2 == NULL) phead->next = pHead1;

    return head->next; //返回头结点
}

发表于 2023-03-29 16:49:56 回复(2)
C
牛客57924907号头像 牛客57924907号
if(pHead1==NULL&&pHead2==NULL)
     {
          return NULL;//先判断特殊情况传入了两个空节点，直接返回NULL
     }
    struct ListNode *firstnode1=pHead1;
    struct ListNode *firstnode2=pHead2;
    while(firstnode1->next!=NULL)
      {
         firstnode1=firstnode1->next;
         

      }struct ListNode *last=NULL;
      firstnode1->next=firstnode2;//将两个链表接起来
     
     //利用冒泡排序将他们重新排序
     while(last!=pHead1->next){
      struct ListNode *pre=pHead1;
      struct ListNode *cur=pHead1->next;
     
      while(cur!=last)
        {  if(pre->val>cur->val)
             {
                int temp=pre->val;
                pre->val=cur->val;
                cur->val=temp;
             }
            pre=pre->next;
            cur=cur->next;
        }  last=pre;
     }    
     return pHead1;
发表于 2023-03-15 18:26:00 回复(0)
C
深情的考拉整顿职场头像 深情的考拉整顿职场 
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode node;
    struct ListNode *pHead = &node;
    struct ListNode *cur = pHead;
    while (1) {
        if (pHead1 == 0) { cur->next = pHead2; break; }
        if (pHead2 == 0) { cur->next = pHead1; break; }
        if (pHead1->val < pHead2->val){
            cur->next = pHead1;
            cur = cur->next;
            pHead1 = pHead1->next;
        }
        else {
            cur->next = pHead2;
            cur = cur->next;
            pHead2 = pHead2->next;
        }
    }
    return pHead->next;
}

发表于 2023-03-11 23:08:30 回复(0)
C
划船全靠浪呀头像 划船全靠浪呀
这应该是C语言最简洁的递归了 
struct ListNode* Merge(struct ListNode* phead1, struct ListNode* phead2 ) {
    if(phead1==NULL) return phead2;
    if(phead2==NULL) return phead1;
    if(phead1->val<=phead2->val){
        phead1->next=Merge(phead1->next,phead2);
        return  phead1;
    }
    else{
        phead2->next=Merge(phead1,phead2->next);
        return  phead2;
    }
}


发表于 2022-11-24 17:46:45 回复(0)
C
厚礼谢头像 厚礼谢
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */

/**
 * 
 * @param pHead1 ListNode类 
 * @param pHead2 ListNode类 
 * @return ListNode类
 */
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here

    if(pHead1 == NULL || pHead2 == NULL)
        return pHead1 == NULL ? pHead2 : pHead1;

    if(pHead1->val <= pHead2->val)
    {
        pHead1->next = Merge(pHead1->next,pHead2);
        return pHead1;
    }
    else
    {
        pHead2->next = Merge(pHead2->next, pHead1);
        return pHead2;
    }
    
}
发表于 2022-11-12 21:04:33 回复(0)
C
80后大叔头像 80后大叔 
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    if(pHead1==NULL && pHead2 == NULL) return NULL;
    if(pHead1==NULL) return pHead2;
    if(pHead2==NULL) return pHead1;
    struct ListNode* p=pHead1;
    struct ListNode* q=pHead2;
    if(pHead1->val<pHead2->val) { // p指向头结点较小的链表
        p=pHead1;
        q=pHead2;
    } else {
        p=pHead2;
        q=pHead1;
    }
    struct ListNode* head=p;
    while(p!=NULL || q!=NULL){
        if(p->next==NULL && q!=NULL) { // 链表1到尾部了
            p->next=q;
            break;
        }
        if(q==NULL) break; // 链表2到尾部了
        if(p->val<=q->val && p->next->val>=q->val) {
            struct ListNode* tmp = p->next;
            struct ListNode* tmp2 = q->next;
            p->next = q;
            p->next->next=tmp;
            q=tmp2;
        } 
        p=p->next;
    }
    return head;
}
发表于 2022-11-08 19:29:55 回复(0)
C
取nm名字全被取了头像 取nm名字全被取了 
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) 
{
    struct ListNode *p = pHead1;
    struct ListNode *q = NULL;
    struct ListNode *temp;
    int val;
    if(!pHead1 || !pHead2)
    {
        return !pHead1 ? pHead2 : pHead1;
    }
    while(p->next)
    {
        p = p->next;
    }
    p->next = pHead2;
    p = pHead1;
    while(p)
    {
        temp = p;
        q = p;
        while(q)
        {
            if(temp->val > q->val)
            {
                temp = q;
            }
            q = q->next;
        }
        val = p->val;
        p->val = temp->val;
        temp->val = val;
        p = p->next;
    }
    return pHead1;
    // write code here
}

发表于 2022-11-02 21:20:01 回复(0)
提交观点

问题信息

链表 2021
来自：2021届阅文测试开发...
难度：
45条回答 172097浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号