实现有序链表merge函数时出现垃圾值/段错误，求技术排查

我来帮你梳理下代码里的问题，顺便给你两种可行的解决方案：

你的代码里的核心问题 #

1. 未完成的合并循环导致数组存垃圾值 #

你代码最后那段while(leftpos<=m...没写完，这会让newarr后半部分的元素没被正确赋值，还是内存里的随机垃圾值，打印的时候自然会出问题。

2. 没把排序后的数组写回链表 #

就算你补完了循环，当前代码也没把newarr里的排序后的值放回链表节点，等于白做了数组排序，链表还是原来的无序状态。

3. 变长数组的栈溢出风险 #

你用的int arr[len];是C99的变长数组，如果链表节点数太多，栈空间不够就会触发段错误，不如用动态分配的数组更稳妥。

4. 没必要的数组转换逻辑 #

既然两个输入链表本身就是有序的，直接操作链表节点合并才是最高效的，完全没必要转成数组再折腾，既浪费内存又容易出错。

修复后的数组转换版本代码 #

如果你坚持要保留数组转换的思路，这是补全并修复后的完整代码：

#include <stdio.h>
#include <stdlib.h>

typedef struct _node { int data; struct _node * next; } node_t; 
typedef struct { node_t * head; node_t * tail; } LL_t; 

LL_t* createList(int num_nodes); 
void printList(LL_t* L); 

void merge(LL_t * L, LL_t * L2){ 
    if(L2->head == NULL){ // 处理L2为空的情况
        free(L2); 
        return; 
    } 
    else if(L->head == NULL){ // 处理L1为空的情况
        *L = *L2; 
        free(L2); 
        return; 
    } 

    // 计算L1的最后一个节点索引mid
    node_t* node = L->head;
    int mid = 0;
    while (node->next != NULL) {
        mid++;
        node = node->next;
    }
    // 连接两个链表
    L->tail->next = L2->head; 
    L->tail = L2->tail; 

    // 统计总节点数
    int len = 0;
    node_t* ind = L->head;
    while (ind != NULL) {
        len++;
        ind = ind->next;
    }

    // 动态分配数组，避免栈溢出
    int* arr = (int*)malloc(len * sizeof(int));
    int* newarr = (int*)malloc(len * sizeof(int));
    if (!arr || !newarr) {
        // 内存分配失败的容错处理
        free(arr);
        free(newarr);
        free(L2);
        return;
    }

    // 将链表元素存入数组arr
    node_t* cur = L->head;
    for(int i = 0; cur != NULL; i++){ 
        arr[i] = cur->data; 
        cur = cur->next; 
    } 

    // 归并两个有序子数组到newarr
    int leftpos = 0;
    int rightpos = mid + 1;
    int newpos = 0;

    // 合并两个有序段
    while(leftpos <= mid && rightpos <= len - 1){ 
        if(arr[leftpos] < arr[rightpos]){ 
            newarr[newpos++] = arr[leftpos++]; 
        } else {
            newarr[newpos++] = arr[rightpos++]; 
        }
    } 
    // 填充左半部分剩余元素
    while(leftpos <= mid){
        newarr[newpos++] = arr[leftpos++];
    }
    // 填充右半部分剩余元素
    while(rightpos <= len - 1){
        newarr[newpos++] = arr[rightpos++];
    }

    // 将排序后的数组写回链表
    cur = L->head;
    for(int i = 0; cur != NULL; i++){
        cur->data = newarr[i];
        cur = cur->next;
    }

    // 释放动态分配的内存和L2结构体
    free(arr);
    free(newarr);
    free(L2);
}

更高效的链表直接合并方案 #

这是处理有序链表合并的标准解法，直接操作节点，时间复杂度O(n+m)，空间复杂度O(1)，完全避开数组相关的问题：

void merge(LL_t * L, LL_t * L2){ 
    if(L2->head == NULL){ // L2为空，直接释放
        free(L2); 
        return; 
    } 
    else if(L->head == NULL){ // L1为空，直接接管L2的内容
        *L = *L2; 
        free(L2); 
        return; 
    } 

    // 用dummy节点简化头节点的处理逻辑
    node_t dummy;
    dummy.next = NULL;
    node_t* current = &dummy;

    node_t* p1 = L->head;
    node_t* p2 = L2->head;

    // 逐个比较两个链表的节点，选择较小的接入结果
    while(p1 != NULL && p2 != NULL){
        if(p1->data < p2->data){
            current->next = p1;
            p1 = p1->next;
        } else {
            current->next = p2;
            p2 = p2->next;
        }
        current = current->next;
    }

    // 接入剩余的节点
    if(p1 != NULL){
        current->next = p1;
    } else {
        current->next = p2;
        L->tail = L2->tail; // 如果剩余的是L2的节点，更新L的尾指针
    }

    // 更新L的头指针
    L->head = dummy.next;

    // 释放L2的结构体（注意：L2的节点已经合并到L中，不能释放节点）
    free(L2);
}

小提示 #

如果是刷题或者实际项目中，优先用链表直接合并的方案，不仅效率更高，还能避免数组带来的各种内存问题。

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