在 C 中合并两个排序列表

我一直在尝试调试这段将两个排序列表合并为一个排序列表的代码,我从 leetcode

编写了这个问题
typedef struct{
   int val;
   struct ListNode *next;
}ListNode;
 

ListNode* mergeTwoLists(ListNode* l1,ListNode* l2){
        ListNode* head=(l1!=NULL||l2!=NULL)?(ListNode*)malloc(sizeof(ListNode)):NULL;
        ListNode* temp=head;
        ListNode* temp1=l1;
        ListNode* temp2=l2;
        if(temp!=NULL){
        while(temp1!=NULL&&temp2!=NULL){
                temp->val=(temp1->val<=temp2->val)?temp1->val:temp2->val;
                temp->next=(ListNode*)malloc(sizeof(ListNode));
                temp=temp->next;
                if(temp1->val<=temp2->val){
                        temp1=temp1->next;
                }else{
                        temp2=temp2->next;
                }
        }
        ListNode* temp3=(temp1!=NULL)?temp1:temp2;
        while(temp3!=NULL){
                temp->val=temp3->val;
                temp3=temp3->next;
                if(temp3!=NULL){
                        temp->next=(ListNode*)malloc(sizeof(ListNode));
                }else{
                        temp->next=NULL;
                }
        }
        }
        return head;
}

逻辑对我来说似乎很好,但如果我们举个例子
假设我们将这两个列表传入 ListNode* mergeTwoLists(ListNode* l1,ListNode* l2)
l1->(1)->(3)->(4)->NULL
l2->(5)->(6)->(7)->NULL
我的结果:head->(1)->(3)->(4)->(7)->NULL
它应该是什么:head->(1)->(3)->(4)->(5)->(6)->(7)->NULL

zhenzhengdeyu 回答:在 C 中合并两个排序列表

问题是第二个循环:

ListNode* temp3=(temp1!=NULL)?temp1:temp2;
while(temp3!=NULL){
    temp->val=temp3->val;
    temp3=temp3->next;
    if(temp3!=NULL){
        temp->next=(ListNode*)malloc(sizeof(ListNode));

        /* 1 */
        temp = temp->next;
    }else{
        temp->next=NULL;
    }
}

标记 1:您为列表创建了一个新元素,但实际上并没有使用它!这就是为什么所有信息都被放置在同一个节点中,并且您的输出仅显示第二个列表的最后一个元素。输入 temp = temp->next; 可以解决问题。

编辑:关于您的 struct 定义:

typedef struct{
   int val;
   struct ListNode *next;
}ListNode;

它在我的测试代码中抛出了大量警告。建议改为:

typedef struct listnode_t {
   int val;
   struct listnode_t *next;
} ListNode;
,

让我们也合并你的两个 while 循环!

  • 遍历两个列表
  • 如果第一个列表有 NULL 值,则分配第二个列表的值,反之亦然
  • 如果两个列表都不是空的,则检查值并分配最低值。
  • 如果至少有一个列表项(迭代器)不为空,则循环将在循环结束后将 null 分配给最后一个节点的下一个。
ListNode* mergeTwoLists(ListNode* l1,ListNode* l2){
    ListNode* head=(l1!=NULL||l2!=NULL)?(ListNode*)malloc(sizeof(ListNode)):NULL;
    ListNode* temp=head;
    ListNode* temp1=l1;
    ListNode* temp2=l2;
    
    while(temp1!=NULL || temp2!=NULL){
        if (temp1==NULL){
            temp->val = temp2->val;
            temp->next=(ListNode*)malloc(sizeof(ListNode));
            temp = temp->next;
            temp2 = temp2->next;
        }
        if(temp2==NULL){
            temp->val = temp1->val;
            temp->next=(ListNode*)malloc(sizeof(ListNode));
            temp = temp->next;
            temp1 = temp1->next;
        }
        if (temp1->val<=temp2->val){
            temp->val = temp1->val;
            temp->next=(ListNode*)malloc(sizeof(ListNode));
            temp = temp->next;
            temp1=temp1->next;
        }else{
            temp->val = temp2->val;
            temp->next=(ListNode*)malloc(sizeof(ListNode));
            temp = temp->next;
            temp1=temp2->next;
        }
        
    }
    if(temp==NULL){
       temp->next = NULL;
    }
    return head;
}

让我知道这是否有效。

本文链接:https://www.f2er.com/3315.html

大家都在问