合并两个链表时触发Segmentation Fault (core dumped)的原因排查

尝试合并两个链表（1->2->4和1->3->4）时触发Segmentation fault (core dumped)。即使对链表结构执行malloc操作后问题仍未解决，程序在调用merge函数前运行正常，调试器也未检测到错误。

原代码 #

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

typedef struct node
{
    int val;
    struct node *next;
} node;

typedef struct linkedlist
{
    node *head;
    node *tail;
} linkedlist;

void createlinkedlist(linkedlist *l)
{
    l->head = NULL;
    l->tail = NULL;
}

void push(linkedlist *l, int value)
{
    node *newnode = (node *)malloc(sizeof(node));
    if (newnode == NULL)
    {
        printf("insertion failed");
        return;
    }
    newnode->val = value;
    newnode->next = NULL;
    if (l->tail != NULL)
    {
        l->tail->next = newnode;
    }
    l->tail = newnode;
    if (l->head == NULL)
    {
        l->head = newnode;
    }
}

void display(linkedlist *l)
{
    node *printval = l->head;
    printf("\n");
    while (printval != NULL)
    {
        printf("%d-->", printval->val);
        printval = printval->next;
    }
}

void merge(linkedlist *l, linkedlist *k)
{
    node *lnext = l->head->next;
    node *lprevious = l->head;
    node *rprevious = k->head;
    node *rnext = k->head->next;
    if ((lprevious->val) <= (rprevious->val))
    {
        node *h = lprevious;
        while (lprevious != NULL && rprevious != NULL)
        {
            if (lprevious->val <= rprevious->val)
            {
                lprevious->next = rprevious;
                rprevious->next = lnext;
                rprevious = rnext;
                rnext = rnext->next;
                lprevious = lprevious->next;
            }
            else
            {
                lprevious = lprevious->next;
                lnext = lnext->next;
            }
        }
        l->head = h;
    }
    else
    {
        // node *h = head2;
        // while (previous != NULL || head2 != NULL) {
    }
}

int main()
{
    linkedlist l;
    linkedlist k;
    createlinkedlist(&l);
    createlinkedlist(&k);
    push(&l, 1);
    push(&l, 2);
    push(&l, 4);

    push(&k, 1);
    push(&k, 3);
    push(&k, 4);
    display(&k);
    display(&l);
    merge(&l, &k);
    display(&l);
}

运行输出 #

1-->3-->4-->
Segmentation fault (core dumped)

段错误原因分析 #

1. 空指针访问：在merge函数中，当处理完k链表的最后一个节点时，rnext会变为NULL，此时执行rnext = rnext->next会直接访问空指针的成员，触发段错误。
2. 遍历逻辑漏洞：合并时的指针移动逻辑混乱，比如将rprevious插入l链表后，lnext的指向没有随着l链表的推进正确更新，导致后续节点链接错误。
3. 未处理链表遍历完成的情况：当其中一个链表的节点先被遍历完时，没有将另一个链表的剩余节点直接链接到合并后的链表末尾，可能导致非法访问。
4. else分支未实现：如果l链表的头节点值大于k链表的头节点，merge函数的else分支为空，会导致后续逻辑缺失，可能引发未定义行为。
5. 未检查空链表：merge函数没有处理l或k链表为空的情况，若任一链表为空，直接访问l->head->next或k->head->next会触发空指针访问。

修复后的代码 #

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

typedef struct node
{
    int val;
    struct node *next;
} node;

typedef struct linkedlist
{
    node *head;
    node *tail;
} linkedlist;

void createlinkedlist(linkedlist *l)
{
    l->head = NULL;
    l->tail = NULL;
}

void push(linkedlist *l, int value)
{
    node *newnode = (node *)malloc(sizeof(node));
    if (newnode == NULL)
    {
        printf("insertion failed");
        return;
    }
    newnode->val = value;
    newnode->next = NULL;
    if (l->tail != NULL)
    {
        l->tail->next = newnode;
    }
    l->tail = newnode;
    if (l->head == NULL)
    {
        l->head = newnode;
    }
}

void display(linkedlist *l)
{
    node *printval = l->head;
    printf("\n");
    while (printval != NULL)
    {
        printf("%d-->", printval->val);
        printval = printval->next;
    }
}

void merge(linkedlist *l, linkedlist *k)
{
    // 处理空链表情况
    if (l->head == NULL) {
        *l = *k;
        return;
    }
    if (k->head == NULL) {
        return;
    }

    node *current_l = l->head;
    node *current_k = k->head;
    node *merged_head = NULL;
    node *merged_tail = NULL;

    // 确定合并后的头节点
    if (current_l->val <= current_k->val) {
        merged_head = current_l;
        merged_tail = current_l;
        current_l = current_l->next;
    } else {
        merged_head = current_k;
        merged_tail = current_k;
        current_k = current_k->next;
    }

    // 遍历两个链表，合并节点
    while (current_l != NULL && current_k != NULL) {
        if (current_l->val <= current_k->val) {
            merged_tail->next = current_l;
            merged_tail = current_l;
            current_l = current_l->next;
        } else {
            merged_tail->next = current_k;
            merged_tail = current_k;
            current_k = current_k->next;
        }
    }

    // 链接剩余节点
    if (current_l != NULL) {
        merged_tail->next = current_l;
        merged_tail = l->tail; // 原l的tail是最后一个节点
    } else {
        merged_tail->next = current_k;
        merged_tail = k->tail; // 原k的tail是最后一个节点
    }

    // 更新原l链表的head和tail
    l->head = merged_head;
    l->tail = merged_tail;

    // 清空k链表（可选，避免野指针）
    k->head = NULL;
    k->tail = NULL;
}

int main()
{
    linkedlist l;
    linkedlist k;
    createlinkedlist(&l);
    createlinkedlist(&k);
    push(&l, 1);
    push(&l, 2);
    push(&l, 4);

    push(&k, 1);
    push(&k, 3);
    push(&k, 4);
    display(&k);
    display(&l);
    merge(&l, &k);
    display(&l);
}

修复说明 #

• 增加了空链表检查，避免空指针访问；
• 重新设计合并逻辑，使用merged_head和merged_tail指针跟踪合并后的链表，逻辑更清晰；
• 处理了其中一个链表遍历完成后剩余节点的链接；
• 实现了两种头节点大小情况的处理；
• 更新了合并后链表的tail指针，保证链表结构完整；
• 可选清空k链表，避免后续操作出现野指针问题。

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