C语言 尝试按降序合并链表

Question

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

/*
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都无效。