c - 如何在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;
}