c - 尝试按降序合并链表

Question

所以我有两个链表，链表是我自己的 Node 实现。出于某种原因，我有将两个列表合并到位的代码，该代码应该添加最少的值，然后向下移动两个列表，始终检查哪个最小并将其添加到新列表中。出于某种原因，我的代码合并了两个列表，但不是按升序排列。

/*
Takes two lists and merges them without creating extra nodes. */
Node *merge(Node* list1, Node* list2) {
    Node *mergelist, *cur1, *cur2, *curm, *prevm;

    cur1 = list1, cur2 = list2;
    mergelist = NULL;

    while (cur1 != NULL || cur2 != NULL) {
        // List2:node < List1:node
        if (cur1 != NULL && cur2 != NULL && cur2->value < cur1->value) {
            curm = cur2;
            cur2 = cur2->next;
            curm->next = NULL;
        }

        // List2:node <= List1:node
        else if (cur1 != NULL && cur2 != NULL && cur1->value <= cur2->value) {
            curm = cur1;
            cur1 = cur1->next;
            curm->next = NULL;
        }

        // List2: have remaining nodes, List1: not
        else if (cur2 != NULL && cur1 == NULL) {
            curm = cur2;
            cur2 = cur2->next;
            curm->next = NULL;
        }

        // List1: have remaining nodes, List2: not
        else if (cur1 != NULL && cur2 == NULL) {
            curm = cur1;
            cur1 = cur1->next;
            curm->next = NULL;
        }

        // check if mergelist is empty 
        // add current node as first node to it
        if (mergelist == NULL) {
            mergelist = curm;
            prevm = mergelist;
        }
        // add current node to the tail of new merged list
        else {
            prevm->next = curm;
            prevm = prevm->next;
        }
    }

    //Sort list

    return mergelist;
}

例子:

MERGE TEST
List 1: 9 9 5 5 3 3
List 2: 10 10 6 6 1 1
List 1 + 2 Merged:
Merged list: 9 9 5 5 3 3 10 10 6 6 1 1

它并排合并列表，而不是按升序合并。任何想法为什么？
编辑:我不能使用嵌套循环。可能只存在一个循环。

Answer 1

您只能在列表排序时使用您的合并算法。这也应该是您拥有的最佳选择，排序然后合并。它比合并然后排序具有更好的运行时复杂性。所以保留你的算法，但添加排序。注意正确的排序顺序。 (在您的示例中，排序顺序被翻转了)。

但除此之外，您不应该像在循环结束时那样使用 mergeList。而是直接构建列表。看代码:

/*
Takes two lists and merges them without creating extra nodes. */
Node *merge(Node* list1, Node* list2) {
    Node *mergelist, *cur1, *cur2, *curm, *prevm;
    cur1 = list1, cur2 = list2;
    curm = mergelist;

    while (cur1 != NULL || cur2 != NULL) {
        if ((cur1 != NULL && cur2 != NULL && cur2->value < cur1->value) || (cur2 != NULL && cur1 == NULL)) {
            curm->next = cur2;
            curm = curm->next;
            cur2 = cur2->next;

        } else if ((cur1 != NULL && cur2 != NULL && cur1->value <= cur2->value) || (cur1 != NULL && cur2 == NULL)) {
            curm->next = cur1;
            curm = curm->next;
            cur1 = cur1->next;
        }
    }
    return mergelist->next;
}