在c中合并两个排序列表

Question

我一直在尝试调试这段代码，将两个排序列表合并为一个排序列表，我从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

Answer 1

问题是第二个循环:

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;

Answer 2

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

• 遍历两个列表
• 如果第一个列表的值为NULL，则分配第二个列表的值，反之亦然
• 如果两个列表都不是空的，那么检查值并分配最小的值。
• While循环将如果至少有一个列表项(迭代器)不为空，并在循环结束后将最后一个节点的下一个节点赋值为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;
}

让我知道这是否有效。