在 C 中合并两个链表时遇到问题

Question

我应该编写一个函数来合并(将一个放在另一个的末尾)两个单向链表。用户在控制台中输入一系列数字，例如：1 2 3 4 0(0 表示输入结束，不是列表的元素)。这些数字被放入链表中，列表现在看起来像这样：1 2 3 4。这个过程再次重复，直到我们有两个不同的链表。然后合并函数称为"void merge(struct Node head1， struct Node head2)"。程序在打印新列表后结束。

我的思考过程是首先将指针指向第一个列表的末尾，然后创建一个 while 循环，该循环将遍历另一个列表，并使第一个列表的下一个元素成为第二个列表的当前元素。

typedef struct Element Element;
struct Element
{
int data;
Element *next;
};
Element *addNew(int data)
{
Element *newN = (Element*)malloc(sizeof(Element));
newN->data = data;
newN->next = NULL;
return newN;
}
Element *add_on_beginning(Element *head, Element *newN)
{
newN->next = head;
return newN;
}
Element *add_on_end(Element *head, Element *newN)
{
if(head == NULL)
{
return newN;
}
Element *temp = head;
while(temp->next != NULL)
{
temp = temp->next;
}
temp->next = newN;
return head;
}
void printElement(Element *element)
{
printf("%d ", element->data);
}
void printList(Element *head)
{
Element *temp = head;
while(temp != NULL)
{
printElement(temp);
temp = temp->next;
}
}
void merge(Element *head1, Element *head2)
{
Element *temp1 = head1;
Element *temp2 = head2;
while(temp1->next != NULL)
{
temp1 = temp1->next;
}
while(temp2->next != NULL)
{
temp1->next = temp2;
temp2 = temp2->next;
}
}
int main()
{
Element *head1 = NULL;
Element *head2 = NULL;
int arr[1000];
char temp1;
char temp2;
int i = 0;
int j = 0;
printf("Input the first set of elements: n");
while(temp1 != 'n')
{
scanf("%d%c", &arr[i], &temp1);
if(arr[i] == 0)
{
break;
}
head1 = add_on_end(head1, addNew(arr[i]));
i++;
}
printf("Input the second set of elements: n");
while(temp2 != 'n')
{
scanf("%d%c", &arr[j], &temp2);
if(arr[j] == 0)
{
break;
}
head2 = add_on_end(head2, addNew(arr[j]));
j++;
}
merge(head1, head2);
printList(head1);
return 0;
}

因此，出于某种原因，该函数仅读取第二个列表的最后两个元素。

输入：

1 2 3 4 0
5 6 7 8 0

输出：

1 2 3 4 7 8

我应该得到的结果是

输入：

1 2 3 4 0
5 6 7 8 0

输出：

1 2 3 4 5 6 7 8

Answer 1

想想"代码重用"。 您已经编写了所需的功能。重用它...

printList( add_on_end( head1, head2 ) );

您已使用malloc()从堆中获取节点空间。main()会立即退出，但最好至少在评论中确认您没有反复调用free()。

编辑printList()可以转移到main()及其对链表的"最终遍历"，用于对free()进行这些调用。

Answer 2

此函数

void merge(Element *head1, Element *head2)
{
Element *temp1 = head1;
Element *temp2 = head2;
while(temp1->next != NULL)
{
temp1 = temp1->next;
}
while(temp2->next != NULL)
{
temp1->next = temp2;
temp2 = temp2->next;
}
}

无效。

首先，它不会更改原始指针 head1 和 head2，因为它们是按值传递给函数的。因此，该函数处理原始指针的副本。

其次，在函数中没有检查head1或head2是否等于NULL。

函数可以通过以下方式定义

void merge( Element **head1, Element **head2 )
{
if ( *head1 == NULL )
{
*head1 = *head2;
*head2 = NULL;
}
else if ( *head2 != NULL )
{
while ( *head1 != NULL ) head1 = &( *head1 )->next;
for ( ; *head2 != NULL; head2 = &( *head2 )->next )
{
*head1 = *head2;
head1 = &( *head1 )->next;
}
}              
}

请注意，没有必要声明一个数组来输入列表中的数据。

还有这些同时循环

char temp1;
char temp2;
int i = 0;
int j = 0;
printf("Input the first set of elements: n");
while(temp1 != 'n')
//..

和

while(temp2 != 'n')
//...

具有未定义的行为，因为temp1和temp2都没有初始化。

Answer 3

你的问题之一是：

while(temp2->next != NULL) {
temp1->next = temp2;
temp2 = temp2->next;
}

您不会更新 temp1 的值。

另外，你为什么不直接而不是这一秒同时做：

temp1->next = temp2;

我的意思是链表 2 已正确链接，您只需要将第一个列表的末尾与第二个列表的开头链接即可。