我试图按升序合并两个排序的链表，但我没有得到正确的输出

Question

我正在尝试合并两个已排序的链表，但没有得到任何输出，我试图遍历两个链表，同时比较数据并将较小的元素添加到我的最终链表中。我正在使用 pushback() 在末尾添加元素：

void merge_sort(struct node *a, struct node *b)
{
    struct node *ans = (struct node *)malloc(sizeof(struct node));
    ans = NULL;
    while (a != NULL || b != NULL)
    {
        if ((a->data >= b->data) || (a == NULL && b != NULL))
        {
            pushback(&ans, b->data);
            b = b->next;
            // display(ans);
        }
        if ((b->data > a->data) || (b == NULL && a != NULL))
        {
            pushback(&ans, a->data);
            a = a->next;
            // display(ans);
        }
    }
    display(ans);
}

Answer 1

void merge_sort(struct node *a, struct node *b)
{
    struct node *ans = (struct node *)malloc(sizeof(struct node));
    ans = NULL;
    while (a != NULL && b != NULL)
    {
        
        if ((a->data >= b->data))
        {
            pushback(&ans, b->data);
            b = b->next;
            // display(ans);
        }
        else if ((b->data > a->data))
        {
            pushback(&ans, a->data);
            a = a->next;
            // display(ans);
        }
        
    }
    while(a != NULL)
    {
       pushback(&ans,a->data);
       a=a->next;
    }
    while(b != NULL)
    {
       pushback(&ans,b->data);
       b=b->next;
    }
    display(ans);
}

在您的解决方案中，您将错过链表长度不相同的情况，以及特定链表的元素越过的情况。试试这个，如果你正确定义了 display() 和 pushback() 函数，它会很好地工作。
您还必须提及链表排序的确切顺序（在这种情况下，您可能必须在应用此算法之前反转链表）

如果您提供包括所有函数的定义以及输出片段的完整代码会更好，这样我们就可以知道可能是什么问题

Answer 2

标准解，使用pointer-to-pointer:

struct node * merge_sort(struct node *one, struct node *two)
{
    struct node *ans , **pp;

    ans = NULL;
    for(pp = &ans; one && two; pp = &(*pp)->next) {
        
        if (one->data <= two->data) {
            *pp = one;
            one = one->next;
        }
        else    {
            *pp = two;
            two = two->next;
            }
        
    }
        /* At this point, either one or two is exhausted.
        ** or both: in that case NULL will be assigned to *pp
        */
    *pp = (one) ? one : two;

    return ans;
}

Answer 3

您的方法存在多个问题：

您没有合并列表，而是尝试使用 2 个列表中的值构建第三个列表。
你为ans分配了一个初始节点，但你立即设置ans = NULL;从而丢失了对分配内存的引用，导致内存泄漏。
不清楚 push_back 的作用，因为它不是标准函数，您既不提供源代码也不提供规范。

a

b

testing (a->data >= b->data) 具有未定义的行为。在访问data 成员之前，您应该测试指针 的有效性。

merge_sort 应该 return 新列表 ans.

这是修改后的版本：

struct node *merge_sort(const struct node *a, const struct node *b) { struct node *ans = NULL; while (a != NULL || b != NULL) { if (a != NULL && (b == NULL || a->data <= b->data)) { pushback(&ans, a->data); a = a->next; } else { pushback(&ans, b->data); b = b->next; } } //display(ans); return ans; }

如果您要在不分配任何内存的情况下合并列表，这里有一个替代方案：

struct node *merge_sort(struct node *a, struct node *b) { struct node *ans; struct node **link = &ans; while (a != NULL && b != NULL) { if (a->data <= b->data) { *link = a; link = &a->next; a = a->next; } else { *link = b; link = &b->next; b = b->next; } } *link = (a != NULL) ? a : b; //display(ans); return ans; }

我试图按升序合并两个排序的链表，但我没有得到正确的输出

im trying to merge two sorted linked list in ascending order but im not getting the correct output

c

sorting

merge

linked-list

singly-linked-list