C语言 合并带有头节点和不带新节点的排序链表(void 函数)

Question

我正在编写一个 void 函数void merged_lists (cell * l1, cell * l2, cell * l3);接收两个链表，以l1和l2为首，其内容按非降序排序，并且 生成一个以L3为首的新列表，其中包含排序的L1 和 L2元素。

例如，如果以 l1 为首的列表为 l1 -> 1 -> 7 -> 9 -> 10 -> NULL 且以 l2 为首的列表为 l2 -> 2 -> 3 -> 8 -> 空，则输出必须为l3

-> 1 -> 2 -> 3 -> 7 -> 8 -> 9 -> 10 -> 空这是一个已知分辨率的问题，但我试图在不分配任何新单元格的情况下解决它，只是操作来自 l节点的指针位于l1和l2中。

我的方法：

typedef struct cell {
int data;
struct cell *next;
} cell;
void merged_lists (cell * l1, cell * l2, cell * l3){
if(l1->next == NULL)
l3 = l2->next;
if(l2->next == NULL)
l3 = l1->next;
if(l1->next->data <= l2->next->data)
l3 = l1->next;
else
{
l3 = l2->next;
l2->next->next = l1->next;
}
while(l1->next && list2->next) {
if (l1>next->data > l2->data) {
//Step 1. Save the next pointer
Node *tmp = l1->next; 
//Step 2. Change next pointer to point L2
l1->next = l2;
//Step 3. Move L2 to temp
l2= tmp;
}
//Step 4. Move L1 ahead
l1 = l1->next;
} 
if (!l1->next)
l1->next = l2;


}

在主函数中，我将l3作为参数传递给print(cell * head)

关于如何解决解决方案的一些提示？

Answer 1

此函数声明

void merged_lists (cell * l1, cell * l2, cell * l3);

无效，因为指针按值传递。该函数处理指向列表头节点的原始指针的副本。因此，原始指针不会更改。

下面是一个演示程序，演示如何声明和定义函数。

#include <stdio.h>
#include <stdlib.h>
typedef struct cell 
{
int data;
struct cell *next;
} cell;
size_t append( cell **head, const int a[], size_t n )
{
size_t i = 0;
if ( n )
{
while ( *head != NULL ) head = &( *head )->next;
for ( ; ( i < n ) && ( ( *head = malloc( sizeof( cell ) ) ) != NULL ); i++ )
{
( *head )->data = a[i];
( *head )->next = NULL;
head = &( *head )->next;
}
}
return i;
}
void display( const cell *head )
{
for ( ; head != NULL; head = head->next )
{
printf( "%d -> ", head->data );
}
puts( "NULL" );
}
cell * merged_list( cell **list1, cell **list2 )
{
cell *list3 = NULL;
cell **current = &list3;
while ( *list1 != NULL && *list2 != NULL )
{
if ( ( *list2 )->data < ( *list1 )->data )
{
*current = *list2;
*list2 = ( *list2 )->next;
}
else
{
*current = *list1;
*list1 = ( *list1 )->next;
}
current = &( *current )->next;
}
for ( ; *list1 != NULL; current = &( *current )->next )
{
*current = *list1;
*list1 = ( *list1 )->next;
}
for ( ; *list2 != NULL; current = &( *current )->next )
{
*current = *list2;
*list2 = ( *list2 )->next;
}
return list3;
}
int main(void) 
{
cell *list1 = NULL;
cell *list2 = NULL;
int a1[] = { 1, 7, 9, 10 };
int a2[] = { 2, 3, 8 };
append( &list1, a1, sizeof( a1 ) / sizeof( *a1 ) );
append( &list2, a2, sizeof( a2 ) / sizeof( *a2 ) );
display( list1 );
display( list2 );
putchar( 'n' );
cell *list3 = merged_list( &list1, &list2 );
display( list1 );
display( list2 );
display( list3 );
return 0;
}

程序输出为

1 -> 7 -> 9 -> 10 -> NULL
2 -> 3 -> 8 -> NULL
NULL
NULL
1 -> 2 -> 3 -> 7 -> 8 -> 9 -> 10 -> NULL

函数merged_list可以写得更短

cell * merged_list( cell **list1, cell **list2 )
{
cell *list3 = NULL;
cell **current = &list3;
while ( *list1 != NULL || *list2 != NULL )
{
if ( *list1 == NULL || ( *list2 != NULL && ( *list2 )->data < ( *list1 )->data ) )
{
*current = *list2;
*list2 = ( *list2 )->next;
}
else
{
*current = *list1;
*list1 = ( *list1 )->next;
}
current = &( *current )->next;
}
return list3;
}

Answer 2

我认为如果没有tmp变量，您将无法解决此问题。一旦覆盖列表 1 中下一项的指针，您基本上无法访问列表 1 中当前项之后的所有项。因此，除非您将列表的最后一部分存储在临时变量中，否则这是不可能的。