在尝试合并两个链接列表时，为什么我会出现分段错误（核心转储）？

分段错误是由于合并函数中的逻辑错误而发生的。具体来说，节点链接在一起的方式存在一些问题。

以下是合并函数中的问题：

检查第二个链表中的节点是否应插入到第一个链表中的条件不正确。条件应为 （lprevious->val <= rprevious->val），但当前设置为 （lprevious->val） <= （rprevious->val）。额外的括号不是必需的，会导致比较不正确。

merge 函数假定两个链表都是非空的。但是，应该进行检查以处理一个或两个链表为空的情况。

只要 lprevious 和 rprevious 都不是 NULL，merge 函数中的 while 循环就应该继续。但是，循环的终止条件仅基于 lprevious ！= NULL，如果第二个链表比第一个链表短，则可能导致访问第二个链表的 NULL 指针。

该函数未正确更新合并后第一个链表的尾指针。

要解决这些问题，您可以按如下方式更新合并函数：

void merge(linkedlist *l, linkedlist *k)
{
    node *lprevious = l->head;
    node *rprevious = k->head;

    // Check if either linked list is empty
    if (lprevious == NULL)
    {
        l->head = rprevious;
        l->tail = k->tail;
        return;
    }
    if (rprevious == NULL)
    {
        return;
    }

    if (lprevious->val > rprevious->val)
    {
        // Swap l and k pointers so that l always points to the smaller head
        linkedlist temp = *l;
        *l = *k;
        *k = temp;
    }

    node *lnext;
    node *rnext;

    while (lprevious != NULL && rprevious != NULL)
    {
        lnext = lprevious->next;
        rnext = rprevious->next;

        if (lnext == NULL || lnext->val > rprevious->val)
        {
            // Insert the node from the second list into the first list
            lprevious->next = rprevious;
            rprevious->next = lnext;
            rprevious = rnext;
        }
        lprevious = lprevious->next;
    }

    // Update the tail pointer of the first list if needed
    if (rprevious != NULL)
    {
        l->tail->next = rprevious;
        l->tail = k->tail;
    }
}

通过这些更改，合并功能现在应该可以正常工作。它可以正确处理任一链表为空的情况，并正确地将两个链表中的节点链接在一起。

现在，当您运行程序时，您应该获得链表的正确合并输出：

1-->1-->2-->3-->4-->4-->

该函数存在问题：merge

• node *lnext = l->head->next;如果是空列表，则具有未定义的行为，因为是空指针。ll->head
• 同样的问题node *rnext = k->head->next;
• 同样的问题：如果其中一个列表是空的，或者可能是空指针。if ((lprevious->val) <= (rprevious->val))lpreviousrprevious
• 类似地，在循环过程中，和可能导致未定义的行为，因为和/或可能在循环结束之前变为 null。这实际上是导致您观察到的分段错误的原因。rnext = rnext->next;lnext = lnext->next;whilelnextrnext

该函数应在 的 头部之前插入任何较小的元素，然后迭代保留指向前一个元素的指针。mergerll

这是修改后的版本：

void merge(linkedlist *l, linkedlist *k) {
    node *n = k->head;
    if (n == NULL) {
        // k is an empty list: nothing to do
        return;
    }
    if (l->head == NULL) {
        // l is an empty list: move all elements from k to l
        l->head = k->head;
        l->tail = k->tail;
        k->head = k->tail = NULL;
        return;
    }
    if (l->head->val > n->val) {
        // insert head element of k at head of l
        k->head = n->next;
        n->next = l->head;
        l->head = n;
    }
    node *prev = l->head;
    while ((n = k->head) != NULL) {
        if (prev->next == NULL) {
            // reached end of l: append all elements of k
            prev->next = n;
            l->tail = k->tail;
            break;
        }
        if (prev->next->val > n->val) {
            // insert node n between prev and prev->next
            k->head = n->next;
            n->next = prev->next;
            prev->next = n;
        }
        prev = prev->next;
    }
    // clear the k list
    k->head = k->tail = NULL;
}

您似乎正在尝试按升序合并列表。

您的函数有几个错误。merge

第一个是它没有考虑到通常传递给函数的一个或两个列表可以是空的。在本例中，函数开头的这些语句

node *lnext = l->head->next;
node *rnext = k->head->next;

已调用未定义的行为。

在这些语句的 while 循环中也存在同样的问题

rnext = rnext->next;
lnext = lnext->next;

因为指针 和 可以是 null 指针。rnextlnext

此外，while 循环中的 if 语句中也存在逻辑错误。

至少如果不大于，并不意味着需要在节点后插入节点。lprevious->valrprevious->valrpreviouslprevious

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;
}

另一方面，如果大于 ，则并不意味着您必须移动到第二个节点。lprevious->valrprevious->vallprevious->next

并且该函数不考虑指针，并且它应该改变。l->tailr->tail

如果一开始只是根据给定的两个列表形成一个新列表，然后将第一个列表设置为形成的列表，并将第二个列表设置为空列表，则函数代码会更清晰。

请记住，您还需要编写一个函数，该函数将为列表节点释放所有分配的内存。

此外，函数的参数应具有限定符displayconst

void display( const linkedlist *l)

因为该函数不会更改传递的列表。

并且该函数不应显示任何消息。push

if (newnode == NULL)
{
    printf("insertion failed");
    return;
}

它是函数的调用者将决定是否输出消息。此外，函数的调用者应该有可能知道函数调用的结果。也就是说，函数应通过其返回值向调用方报告失败或成功。

下面是一个演示程序，展示了如何实现该功能。merge

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

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

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


int push( linkedlist *l, int value )
{
    node *newnode = malloc( sizeof( node ) );
    int success = newnode != NULL;

    if (success)
    {
        newnode->val = value;
        newnode->next = NULL;

        if (l->head == NULL)
        {
            l->head = newnode;
        }
        else
        {
            l->tail->next = newnode;
        }

        l->tail = newnode;
    }

    return success;
}

void merge( linkedlist *l, linkedlist *r )
{
    node *head = NULL;
    node *tail = NULL;

    node **current = &head;

    while (l->head != NULL && r->head != NULL)
    {
        if (r->head->val < l->head->val)
        {
            *current = r->head;
            r->head  = r->head->next;
        }
        else
        {
            *current = l->head;
            l->head  = l->head->next;
        }

        tail = *current;
        current = &( *current )->next;
    }

    if (l->head != NULL)
    {
        *current = l->head;
        tail = l->tail;
    }

    if ( r->head != NULL )
    {
        *current = r->head;
        tail = r->tail;
    }

    l->head = head;
    l->tail = tail;

    r->head = r->tail = NULL;
}

FILE *display( const linkedlist *l, FILE *fp )
{
    for (const node *current = l->head; current != NULL; current = current->next)
    {
        fprintf( fp, "%d -> ", current->val );
    }

    fputs( "null", fp );

    return fp;
}

void clear( linkedlist *l )
{
    while (l->head)
    {
        node *current = l->head;
        l->head = l->head->next;
        free( current );
    }

    l->tail = l->head;
}

int main( void )
{
    linkedlist l = { .head = NULL, .tail = NULL };

    for (int i = 0; i < 10; i += 2)
    {
        push( &l, i );
    }

    fputc( '\n', display( &l, stdout ) );

    linkedlist r = { .head = NULL, .tail = NULL };

    for (int i = 1; i < 10; i += 2)
    {
        push( &r, i );
    }

    fputc( '\n', display( &r, stdout ) );

    putchar( '\n' );

    merge( &l, &r );

    fputc( '\n', display( &l, stdout ) );
    fputc( '\n', display( &r, stdout ) );

    clear( &l );
}

程序输出为

0 -> 2 -> 4 -> 6 -> 8 -> null
1 -> 3 -> 5 -> 7 -> 9 -> null

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
null

最后还有一句更重要的话。如果要构建排序列表，则应重写该函数以提供按升序插入新节点的功能。push

在这种情况下，该函数可以如下所示

int push( linkedlist *l, int value )
{
    node *newnode = ( node * )malloc( sizeof( node ) );
    int success = newnode != NULL;

    if (success)
    {
        newnode->val = value;

        node **current = &l->head;

        while (*current != NULL && !( newnode->val < ( *current )->val ))
        {
            current = &( *current )->next;
        }

        newnode->next = *current;
        *current = newnode;

        if ( newnode->next == NULL )
        {
            l->tail = newnode;
        }
    }

    return success;
}