首页 > 试题广场 >

合并两个排序的链表

[编程题]合并两个排序的链表
  • 热度指数：1224120 时间限制：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
牛客463694086号头像 牛客463694086号
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    struct ListNode *cur1 = pHead1, *cur2 = pHead2, *head = NULL, *tmp = NULL;

    if (!cur1) {
        return cur2;
    }

    if (!cur2) {
        return cur1;
    }

    if (cur1->val < cur2->val) {
        head = cur1;
        cur1 = cur1->next;
    } else {
        head = cur2;
        cur2 = cur2->next;
    }

    tmp = head;
    while (cur1 && cur2) {
        if (cur1->val < cur2->val) {
            tmp->next = cur1;
            tmp = cur1;
            cur1 = cur1->next;
        } else {
            tmp->next = cur2;
            tmp = cur2;
            cur2 = cur2->next;
        }
    }

    if (cur1) {
        tmp->next = cur1;
    } else if (cur2) {
        tmp->next = cur2;
    }

    return head;
}
发表于 2024-11-22 13:32:41 回复(0)
C
cs小白_头像 cs小白_ 
/**
 * 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 ) {
    // write code here
    struct ListNode*h;
    struct ListNode*p,*q,*r,*s;
    if (pHead1==NULL&&pHead2==NULL) {
        h=NULL;
         
    }
    if (pHead1==NULL&&pHead2!=NULL) {
            printf("%d",pHead2->val);
            h=pHead2;
            q=pHead2->next;
            while(q!=NULL){
                printf(",%d",q->val);
                q=q->next;

            }
            //h=pHead2;
    }
    if (pHead1!=NULL&&pHead2==NULL) {
            printf("%d",pHead1->val);
            h=pHead1;
            p=pHead1->next;
            while(p!=NULL){
                printf(",%d",p->val);
                p=p->next;
            }
            //h=pHead1;
    }
    if (pHead1!=NULL&&pHead2!=NULL) {
        //struct ListNode*p,*q,*r,*s;
        p=pHead1,q=pHead2;
        s=(struct ListNode*)malloc(sizeof(struct ListNode));
        s->val=(pHead1->val<pHead2->val?pHead1->val:pHead2->val);
        s->next=NULL;
        h=s,r=s;
        while (p&&q) {
               s=(struct ListNode*)malloc(sizeof(struct ListNode));
               s->next=r->next;
               if (p->val<=q->val) {
                    s->val=p->val;
                    r->next=s;
                    r=s;
                    p=p->next;
               }
               else {
                    s->val=q->val;
                    r->next=s;
                    r=s;
                    q=q->next;
               }
        }
        if (p==NULL) {
              while (q!=NULL) {
                    s=(struct ListNode*)malloc(sizeof(struct ListNode));
                    s->next=r->next;
                    s->val=q->val;
                    r->next=s;
                    r=s;
                    q=q->next;
              }
              h=h->next;
              printf("%d",h->val);
              r=h->next;
              while (r) {
                    printf(",%d",r->val);
                    r=r->next;
              }
              //return h;
        }
        else {
             while (p!=NULL) {
                    s=(struct ListNode*)malloc(sizeof(struct ListNode));
                    s->next=r->next;
                    s->val=p->val;
                    r->next=s;
                    r=s;
                    p=p->next;
              }
              h=h->next;
              printf("%d",h->val);
              r=h->next;
              while (r) {
                    printf(",%d",r->val);
                    r=r->next;
              }
              //return h;
        }
        
    }
    return h;
}

发表于 2024-11-17 15:45:25 回复(0)
C
鱼也爱下雨头像 鱼也爱下雨
这是官方方法一的c语言版本
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 )
{
        struct ListNode *vhead = (struct ListNode*)malloc(sizeof(struct ListNode));
        struct ListNode *cur = vhead;
        while (pHead1 && pHead2) {
            if (pHead1->val <= pHead2->val) {
                cur->next = pHead1;
                pHead1 = pHead1->next;
            }
            else {
                cur->next = pHead2;
                pHead2 = pHead2->next;
            }
            cur = cur->next;
        }
        cur->next = pHead1 ? pHead1 : pHead2;
        return vhead->next;
}

发表于 2024-09-23 20:39:21 回复(0)
C
Anout头像 Anout 
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2) {
    if(pHead1==NULL)return pHead2;
    if(pHead2==NULL)return pHead1;

    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;

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

    tail->next = pHead1 ? pHead1 : pHead2;

    return head;
}

发表于 2024-08-29 17:28:47 回复(0)
C
牛客72676596号头像 牛客72676596号 
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode* doge=(struct ListNode*)malloc(sizeof(struct ListNode));
    doge->next=pHead1;
    struct ListNode*prev=doge;
    while(pHead1&&pHead2){
        if(pHead1->val>=pHead2->val){
            prev->next=pHead2;
            pHead2=pHead2->next;
        }
        else{
            prev->next=pHead1;
            pHead1=pHead1->next;
        }
        prev=prev->next;
    }
if(pHead1!=NULL){
    prev->next=pHead1;
}
if(pHead2!=NULL){
    prev->next=pHead2;
}
 return doge->next;
}


发表于 2024-08-08 11:14:35 回复(0)
C
terirx头像 terirx 
/**
 * 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
    struct ListNode* temp1 =(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* temp2 =(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* pHead =(struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode* beginHead = NULL;
    temp1 = pHead1;
    temp2 = pHead2;
    if(temp1 == NULL && temp2 ==NULL)
    return NULL;
    if(temp1 == NULL) beginHead = pHead2;
    else if(temp2 == NULL) beginHead = pHead1;
    else if(temp1 -> val > temp2 -> val) beginHead = pHead2;
    else if(temp1 -> val <= temp2 -> val) beginHead = pHead1;
    while(!(temp2 == NULL && temp1 == NULL))
    {
        //当链表为空的时候再取链表指针中的值的时候会报错，所以要提前把边界取出来
        if(temp1 == NULL)
        {
            pHead ->next = temp2;
            pHead = temp2;
            temp2 = temp2 -> next; 
            continue;
        }
        else if(temp2 == NULL)
        {
            pHead -> next = temp1;
            pHead = temp1;
            temp1 = temp1 -> next;
            continue;
        }
        if(temp1 -> val > temp2 -> val)
        {
            pHead ->next = temp2;
            pHead = temp2;
            temp2 = temp2 -> next; 
        }
        else if(temp1 -> val <= temp2 -> val)
        {
            pHead -> next = temp1;
            pHead = temp1;
            temp1 = temp1 -> next;
        }
    }
    return beginHead;
}

发表于 2024-08-07 15:59:56 回复(0)
C
杏花酒旗斜头像 杏花酒旗斜 
大佬们为什么我这里的三个if语句后面两个不加else在输入{1}{2}时会有段错误，而加上else就没有了

#include <stdio.h>
#include <stdlib.h>
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    if (NULL == pHead1) return pHead2;
    if (NULL == pHead2) return pHead1;
    struct ListNode* p1=pHead1;
    struct ListNode* p2=pHead2;
    struct ListNode* p=malloc(sizeof(struct ListNode));
    p->val=-1;
    struct ListNode* tmp=p;
    while (p2!=NULL&&p1!=NULL) {
        if (p1->val>p2->val) {
            tmp->next=p2;
            p2=p2->next;
            tmp=tmp->next;
        }
        else if (p1->val<p2->val) {
            tmp->next=p1;
            p1=p1->next;
            tmp=tmp->next;
        }
        else if (p1->val==p2->val) {
            tmp->next=p1;
            p1=p1->next;
            tmp=tmp->next;
        }
    }
    
    
    if (p1!=NULL) {
        tmp->next=p1;
    }
    if (p2!=NULL) {
        tmp->next=p2;
    }

    return p->next;
}

发表于 2024-07-26 15:56:55 回复(0)
C
Claired头像 Claired 
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    if(pHead1==NULL)
    {
        return pHead2;
    }
    if(pHead2==NULL)
    {
        return pHead1;
    }
    struct ListNode* pHead=NULL;
    if(pHead1->val<=pHead2->val)
    {
        pHead=pHead1;
        pHead1=pHead1->next;
    }
    else {
        pHead=pHead2;
        pHead2=pHead2->next;    
    }
    struct ListNode* cur=pHead;
    
    while(pHead1&&pHead2)
    {
        
        if(pHead1->val<=pHead2->val)
        {
            cur->next=pHead1;
            
            pHead1=pHead1->next;
            //cur=cur->next;
            cur=cur->next;
        }
        else
        {
            cur->next=pHead2;
            
            pHead2=pHead2->next;
            //cur=cur->next;
            cur=cur->next;

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

    return pHead;






}

发表于 2024-07-18 14:46:42 回复(0)
C
饥饿的秋田犬真的会谢头像 饥饿的秋田犬真的会谢 
/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 *
 * @param pHead1 ListNode类
 * @param pHead2 ListNode类
 * @return ListNode类
 */
#include <malloc.h>
#include <stdlib.h>
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    if(pHead1 == NULL && pHead2 == NULL)
        return NULL;
    if(pHead1 != NULL&&pHead2 == NULL)
        return pHead1;
    // write code here
    struct ListNode* p, *q, *C,*r;
    C = (struct ListNode *)malloc(sizeof(struct ListNode));
    r = C;
    r -> next = NULL;
    p = pHead1;
    q = pHead2;
    r = C;
    while (p != NULL && q != NULL){
        if (p -> val < q -> val) {
            r -> next = p;
            r = p;
            p = p -> next;
        }else{
            r -> next = q;
            r = q;
            q = q -> next;
        }
    }
    if(p != NULL)
        q = p;
    if(q != NULL)
        r -> next = q;
    struct ListNode*x = C -> next;
    return x;
}

发表于 2024-07-17 18:17:40 回复(0)
C
准备进厂的猕猴桃很坚定头像 准备进厂的猕猴桃很坚定
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2) {
    // 创建一个哨兵节点(dummy node)，用于简化合并操作
    struct ListNode dummy;

    // tail指针用于跟踪新链表的最后一个节点，初始指向哨兵节点
    struct ListNode* tail = &dummy;

    // 初始化哨兵节点的 next 指针为空
    dummy.next = NULL;

    // 当两个链表都不为空时，进行合并操作
    while (pHead1 != NULL && pHead2 != NULL) {
        // 比较两个链表的当前节点的值，选择较小的节点链接到新链表中
        if (pHead1->val <= pHead2->val) {
            tail->next = pHead1;  // 将pHead1节点链接到新链表中
            pHead1 = pHead1->next;  // 移动pHead1指针到下一个节点
        } else {
            tail->next = pHead2;  // 将pHead2节点链接到新链表中
            pHead2 = pHead2->next;  // 移动pHead2指针到下一个节点
        }
        // 移动tail指针到新链表的最后一个节点
        tail = tail->next;
    }

    // 如果pHead1链表已经遍历完，将pHead2剩余的节点连接到新链表
    if (pHead1 == NULL) {
        tail->next = pHead2;
    }

    // 如果pHead2链表已经遍历完，将pHead1剩余的节点连接到新链表
    if (pHead2 == NULL) {
        tail->next = pHead1;
    }

    // 返回哨兵节点的下一个节点，即合并后的新链表的头节点
    return dummy.next;
}
发表于 2024-06-24 23:25:46 回复(0)
C
勇敢牛牛向前冲呀头像 勇敢牛牛向前冲呀
struct ListNode* Merge(struct ListNode* pHead1, struct ListNode* pHead2 ) {
    // write code here
    struct ListNode* dummyHead=malloc(sizeof(struct ListNode));
    struct ListNode* cur=dummyHead;
    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;
    }
    cur->next=pHead1==NULL?pHead2:pHead1;
    return dummyHead->next;
}
发表于 2024-06-07 20:17:12 回复(0)
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)
提交观点

问题信息

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

热门推荐

通过挑战的用户

查看代码

相关试题

合并两个排序的链表

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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