如何在C语言中正确合并两个链表？附错误代码求详解

嘿，我来帮你理清楚这个问题！首先咱们先拆解你写的代码里的问题，然后再一步步讲两种常见的链表合并场景的正确实现～

先看你写的这段代码：

typedef struct Node{ int val; struct Node *next; }Node; 
/* n1 and n2, head of two linked list */ 
void merge(Node *n1,Node *n2) { 
    Node *tail=n1; 
    while(tail->next!=NULL) 
        tail=tail->next; 
    tail->next=n2; 
}

这段代码的核心问题有两个：

• 没处理空链表边界：如果n1是空链表（也就是n1 == NULL），那tail = n1之后，tail->next就是直接访问空指针，会触发程序崩溃的错误。
• 返回值设计不合理：函数是void类型，调用者没法拿到合并后的链表头——比如当n1为空时，合并后的链表头其实是n2，但你的函数没法把这个信息返回给调用者。

接下来分两种常见的合并场景，给你讲正确的实现方式：

一、简单拼接合并（把n2直接接在n1的末尾） #

如果你的需求只是把第二个链表的所有节点追加到第一个链表的最后，那正确的实现需要补上边界判断，并且返回合并后的链表头：

Node* merge_concat(Node *n1, Node *n2) {
    // 如果n1是空链表，直接返回n2作为合并后的头
    if (n1 == NULL) {
        return n2;
    }
    Node *tail = n1;
    // 遍历找到n1的最后一个节点
    while (tail->next != NULL) {
        tail = tail->next;
    }
    // 把n2接在n1的末尾
    tail->next = n2;
    // 返回合并后的链表头
    return n1;
}

调用的时候就可以这样用：

Node *merged_list = merge_concat(list1, list2);

这样不管list1是不是空，你都能拿到正确的合并后链表的起始地址。

二、有序合并（合并两个有序链表为一个新的有序链表） #

很多时候我们说的“合并链表”，指的是把两个已经按顺序排列（比如升序）的链表，合并成一个新的有序链表。这种情况简单拼接就完全不符合要求了，需要逐个比较节点的值来构建新链表：

迭代实现（更高效，避免递归栈开销） #

Node* merge_sorted(Node *n1, Node *n2) {
    // 创建一个哨兵节点，不用反复判断新链表是否为空
    Node dummy;
    dummy.next = NULL;
    Node *tail = &dummy;

    // 当两个链表都有节点时，选值小的节点接入新链表
    while (n1 != NULL && n2 != NULL) {
        if (n1->val <= n2->val) {
            tail->next = n1;
            n1 = n1->next;
        } else {
            tail->next = n2;
            n2 = n2->next;
        }
        tail = tail->next;
    }

    // 把剩下的非空链表直接接在末尾（剩下的已经是有序的）
    tail->next = (n1 != NULL) ? n1 : n2;

    // 返回合并后的有序链表头（跳过哨兵节点）
    return dummy.next;
}

递归实现（逻辑更简洁，适合理解） #

如果你喜欢递归的写法，逻辑会更直观：

Node* merge_sorted_recursive(Node *n1, Node *n2) {
    // 终止条件：如果一个链表为空，直接返回另一个链表
    if (n1 == NULL) return n2;
    if (n2 == NULL) return n1;

    // 选当前值更小的节点，然后递归合并剩下的部分
    if (n1->val <= n2->val) {
        n1->next = merge_sorted_recursive(n1->next, n2);
        return n1;
    } else {
        n2->next = merge_sorted_recursive(n1, n2->next);
        return n2;
    }
}

最后再总结一下 #

你原来的代码逻辑只覆盖了n1不为空的情况，一旦遇到空链表就会出错。另外返回值设计成void也限制了代码的实用性——毕竟调用者需要知道合并后的链表从哪里开始。

如果只是简单拼接，补上空指针判断+返回头节点就可以；如果是要合并有序链表，就用上面的迭代或递归方法。

内容的提问来源于stack exchange，提问作者drh0use