尝试按降序合并链表

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

Answer 2

不要紧。在调整输入列表之后，我的原始代码工作得很好。谢谢大家。@A1m

/*
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;

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

    return mergelist;
}

测试输出：

##############
MERGE TEST
List 1: list: 1 1 3 3 5 5 9 9
List 2: list: 2 2 6 6 8 8 8 8
List 1 + 2 Merged:
Merged list: 1 1 2 2 3 3 5 5 6 6 8 8 8 8 9 9
##############
MERGE TEST 2
List 3:list: 1 1 2 2 3 3 5 5 6 6 8 8 8 8 9 9
List 4:list: 1 3 9 12
List 3 + List 4 Merged:
list: 1 1 1 2 2 3 3 3 5 5 6 6 8 8 8 8 9 9 9 12
##############

Answer 3

我们初学者应该互相帮助。：)

考虑到您比较两个列表的值的方法只有在两个列表都按降序排序的情况下才有意义，前提是您希望获得一个按升序排序的列表。否则，比较列表的两个节点的值就没有意义了。

给你。

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

typedef struct node
{
    int value;
    struct node *next;
} Node;

Node * merge( Node *list1, Node *list2 )
{
    Node *mergelist = NULL;

    while ( list1 || list2 )
    {

        _Bool second = ( list1 == NULL ) || 
                       ( list2 != NULL && list1->value < list2->value );

        Node *current;

        if ( second )
        {
            current = list2;
            list2 = list2->next;
        }
        else
        {
            current = list1;
            list1 = list1->next;
        }

        current->next = mergelist;
        mergelist = current;
    }

    return mergelist;
}

void display( Node *list )
{
    for ( ; list; list = list->next )
    {
        printf( "%d ", list->value );
    }
}

void insert_array( Node **list, int a[], size_t n )
{
    for ( size_t i = 0; i < n; i++ )
    {
        Node *current = malloc( sizeof( *current ) );
        current->value = a[i];
        current->next = *list;
        *list = current;
        list = &( *list )->next;
    }
}

int main(void) 
{
    int a[] = { 9, 9, 5, 5, 3, 3 };
    int b[] = { 10, 10, 6, 6, 1, 1 };

    Node *list1 = NULL;
    Node *list2 = NULL;

    insert_array( &list1, a, sizeof( a ) / sizeof( *a ) );
    insert_array( &list2, b, sizeof( b ) / sizeof( *b ) );

    display( list1 );
    putchar( '\n' );

    display( list2 );
    putchar( '\n' );

    Node *mergelist = merge( list1, list2 );

    display( mergelist );
    putchar( '\n' );

    return 0;
}

程序输出为

9 9 5 5 3 3 
10 10 6 6 1 1 
1 1 3 3 5 5 6 6 9 9 10 10 

您必须在合并列表的开头插入每个节点。

另外，最好像这样声明函数

Node * merge( Node **list1, Node **list2 );

在退出之前，在函数内部将*list1和*list2设置为NULL，因为在执行函数之后，list1和list2都无效。