链接列表：合并和连接列表的问题

Question

这是我的完整代码。当我尝试连接两个链表然后在下一行合并（按升序）这两个列表时，似乎出现了一些问题。

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

struct Node {
    int data;
    struct Node *next;
} *first = NULL, *second = NULL, *third = NULL, *fourth = NULL; //global pointers

void create1(int a[], int n) {
    first = (struct Node *)malloc(sizeof(struct Node));
    first -> data = a[0];
    first -> next = NULL;
    int i;
    struct Node *t, *last;
    last = first;

    for (i = 1; i < n; i++) {
        t = (struct Node *)malloc(sizeof(struct Node));
        t -> data = a[i];
        t -> next = NULL;
        last->next = t;
        last = t;
    }
}

void create2(int a[], int n) {
    second = (struct Node *)malloc(sizeof(struct Node));
    second->data = a[0];
    second->next = NULL;
    struct Node *t, *last;
    last = second;
    for (int i = 1; i < n; i++) {
        t = (struct Node *)malloc(sizeof(struct Node));
        t->data = a[i];
        t->next = NULL;
        last->next = t;
        last = t;
    }
}

void Display(struct Node *p) {
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
}
void concatenation(struct Node *p, struct Node *q) {
    third = p;
    while (p->next != NULL) {
        p = p->next;
    }
    p->next = q;
}

void mergeLL(struct Node *p, struct Node *q) {
    struct Node *last = NULL;
    if (p->data < q->data) {
        fourth = p;
        last = p;
        p = p->next;
        fourth->next = NULL;
    } else {
        fourth = q;
        last = q;
        q = q->next;
        fourth->next = NULL;
    }

    while (p && q) {
        if (p->data < q->data) {
            last->next = p;
            last = p;
            p = p->next;
        } else {
            last->next = q;
            last = q;
            q = q->next;
        }
        last->next = NULL;
    }
    if (p!=NULL) last->next = p;
    else last->next = q;
}

int main(int argc, char const *argv[])
{
    int a[] = {3,4,5,7,10,15,20,25,25,30};
    int b[] = {2,8,9};
    create1(a, 10); Display(first); printf("\n");
    create2(b, 3);  Display(second); printf("\n");
    mergeLL(first, second);  Display(fourth); printf("\n");
    concatenation(second, first);  Display(third); printf("\n");
    
    return 0;
}

在这里，在主函数中，当我进行合并然后连接时，连接的列表输出会一直持续到无穷大。

但是，当我像这样更改行的顺序时：

concatenation(second, first);  Display(third); printf("\n");
mergeLL(first, second);  Display(fourth); printf("\n");

然后我的合并列表没有被打印。这两个语句都是单独工作的。为什么不在一起？

我多次检查了每个函数，但所有这些对我来说似乎都是正确的。老实说，我什至不知道该怎么做才能修复它。注释掉 main 函数中的 concate 语句给了我正确的结果。当陈述一个接一个地出现时，他们只是没有给我一个正确的结果

P.S：我尝试向 chatGPT 询问同样的事情，但它只是给了我一堆废话。这可能是一个愚蠢的疑问，但请帮忙。

Answer 1

对于初学者来说，在没有理由这样做的情况下声明全局变量是一个坏主意

struct Node {
    int data;
    struct Node *next;
} *first = NULL, *second = NULL, *third = NULL, *fourth = NULL; //global pointers

在这种情况下，您的函数将依赖于全局变量。

在

main

中声明所有必需的指针。

几乎所有函数都是不安全的，并且当使用的指针是空指针时可能会调用未定义的行为。您需要检查指针是否为空指针。

在这种情况下，您可以仅定义一个函数

create

，如下所示

struct Node * create( const int a[], size_t n ) 
{
    struct Node *head = NULL;
    
    for ( struct Node **current = &head; n && ( *current = malloc( sizeof( struct Node ) ) ) != NULL; --n )
    {
        ( *current )->data = *a++;
        ( *current )->next = NULL;
        current = &( *current )->next;
    }

    if ( n != 0 )
    {
        while ( head != NULL )
        {
            struct Node *tmp = head;
            head = head->next;
            free( tmp );
        }
    }

    return head;
}    

在

main

中你可以写

int main( void )
{
    int a[] = { 3, 4, 5, 7, 10, 15, 20, 25, 25, 30 };
    int b[] = { 2, 8, 9 };

    struct Node *first  = create( a, sizeof( a ) / sizeof( *a ) );
    struct Node *second = create( b, sizeof( b ) / sizeof( *b ) );

    //...

请注意，命名函数时应遵循一些约定。所有函数的名称都应以小写字母开头作为函数

create

或以大写字母作为函数

Display

。

重命名后的函数

display

可以如下所示

FILE * display( const struct Node *head, FILE *fp ) 
{
    for ( ; head != NULL; head = head->next )
    {
        fprintf( fp, "%d -> ", head->data );
    }

    fputs( "null", fp );

    return fp;
}

并被称为

main

就像

fputc( '\n', display( first, stdout ) );
fputc( '\n', display( second, stdout ) );

您需要再编写一个函数来释放列表的所有分配内存。

至于你的问题，那么在调用函数

mergeLL

后，两个列表

first

和

second

会相互混合。只需在调用函数后输出列表

first

和

second

，您就会看到

3 -> 4 -> 5 -> 7 -> 8 -> 9 -> 10 -> 15 -> 20 -> 25 -> 25 -> 30 -> null
2 -> 3 -> 4 -> 5 -> 7 -> 8 -> 9 -> 10 -> 15 -> 20 -> 25 -> 25 -> 30 -> null

正如您所见，之后是否调用该函数

concatenation

concatenation(second, first);

值为

next

 的节点的数据成员 

30

 将更改为指向值为 

3

 的节点。因此，结果列表的数据成员 

next

 都不等于 

NULL

。

这两个函数

mergeLL

 和 

concatenation

 要么应该将一个列表中的节点添加到另一个列表，使其中一个列表成为空列表，要么从源列表创建一个新列表，使两个源列表为空，或者为该列表动态分配节点重新创建列表，保持源列表不变。