我試圖按升序合并兩個排序的鏈表，但我沒有得到正確的輸出

我正在嘗試合并兩個已排序的鏈表，但沒有得到任何輸出，我正在嘗試遍歷這兩個鏈表，同時比較資料并將較小的元素添加到我的最終鏈表中。我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);
}

uj5u.com熱心網友回復：

您的方法有多個問題：

• 您不合并串列，而是嘗試使用 2 個串列中的值構造第三個串列。

• 您將初始節點分配給ans，但您立即設定，ans = NULL;從而丟失對分配記憶體的參考，從而導致記憶體泄漏。

• push_back由于它不是標準功能并且您不提供源代碼或規范，因此尚不清楚它是做什么的。

• 如果或是空指標，則測驗(a->data >= b->data)具有未定義的行為。您應該在訪問成員之前測驗指標的有效性。abdata

• merge_sort應該回傳新串列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;
}

uj5u.com熱心網友回復：

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()函式，它會很好地作業。
您還必須提及鏈表排序的確切順序（在這種情況下，您可能必須在應用此演算法之前反轉鏈表）

如果您提供包含所有函式定義以及輸出片段的整個代碼會更好，這樣我們就可以知道可能是什么問題

uj5u.com熱心網友回復：

標準解決方案，使用指標到指標：

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

標籤：C 排序 合并 链表 单链表

上一篇：在Python中對具有不規則列資訊的表進行排序

下一篇：WSL2Nginx PHPFPM在連接到上游時失敗（111：連接被拒絕），客戶端：172.23.0.1，上游：“fastcgi://172.23.0.3:9001”