如何在 C 中合并两个链表

Question

我在 C 中得到了两个排序的链表，我正在尝试将它们合并在一起，以便它们按排序顺序排列。谁能告诉我为什么我的代码不起作用。

struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {
struct ListNode *node;
node = NULL;
struct ListNode *n = (struct ListNode *)malloc(sizeof(struct ListNode));
node = n;
while (l1 != NULL && l2 != NULL) {
if ((*l1).val < (*l2).val) {
(*n).val = (*l1).val;
l1 = (*l1).next;
} else {
(*n).val = (*l2).val;
l2 = (*l2).next;
}
(*n).next = (struct ListNode *)malloc(sizeof(struct ListNode));
n = (*n).next;
}
if (l1 != NULL) {
n = l1;
}
if (l2 != NULL) {
n = l2;
}
return node;
}

Answer 1

• 首先，确定是要合并原始列表，还是要返回列表的副本(但具有相同的值(
• 如果你想要一个副本，你传递的每个输入节点都应该只有一个malloc()。 (你可以验证在合并循环中，l1或l2是高级的，并且(可能(分配了一个节点(

---

#include <stdio.h>
struct node {
struct node *next;
int val;
};
#if WANT_CLONE
#include <stdlib.h>
struct node *clone(struct node *p)
{
struct node *q;
if (!p) return NULL;
q = malloc (sizeof *q);
*q = *p;
return q;
}
#define CLONE(x) clone(x)
#else
#define CLONE(x) (x)
#endif
struct node *merge(struct node *l1, struct node *l2)
{
struct node dummy = {NULL,0}, *here;
for(here = &dummy; l1 || l2; here = here->next) {
if (!l2 || l1 && l1->val <= l2->val) {
here->next= CLONE(l1); l1 = l1->next;
}
else    if(!l1 || l2) {
here->next= CLONE(l2); l2 = l2->next;
}
}
return dummy.next;
}
/* Some test data */
struct node evens[] = {
{evens+1, 0}, {evens+2, 2}, {evens+3, 4}, {evens+4, 6}, {NULL, 8}, };
struct node odds[] = {
{odds+1, 1}, {odds+2, 3}, {odds+3, 5}, {odds+4, 7}, {odds+5, 9}, {NULL, 11}, };
void print(struct node *p)
{
for( ; p; p = p->next) {
printf(" %d", p->val);
}
printf("n");
}
int main(void)
{
struct node *both;
printf("odds:"); print(odds);
printf("evens:"); print(evens);
both = merge(odds, evens);
printf("both:"); print(both);
printf("odds:"); print(odds);
printf("evens:"); print(evens);
return 0;
}

Answer 2

您不是合并 2 个列表，而是创建一个新列表，按递增顺序从两个列表中复制值，但如果列表用尽，则无法复制剩余的元素。

请注意以下额外备注：

• 您可能期望就地合并列表，并返回指向合并列表头部的指针。
• 语法(*l1).val在 C 中并非严格不正确，但指针语法l1->val被认为更具可读性。

这是一个修改版本：

struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode *mergeTwoLists(struct ListNode *l1, struct ListNode *l2) {
struct ListNode *head, *n;
n = head = NULL;
while (l1 != NULL && l2 != NULL) {
if (l1->val <= l2->val) {
if (n == NULL) {
n = head = l1;
} else {
n = n->next = l1;
}
l1 = l1->next;
} else {
if (n == NULL) {
n = head = l2;
} else {
n = n->next = l2;
}
l2 = l2->next;
}
}                
if (l1 != NULL) {
if (n == NULL) {
head = l1;
} else {
n->next = l1;
}
} else {
if (n == NULL) {
head = l2;
} else {
n->next = l2;
}
}
return head;
}