在 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

这个功能

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

注意列表中不需要声明数组来输入数据。

还有这些 while 循环

    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 2

您的问题之一是：

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

您没有更新 temp1 的值。

另外，你为什么不直接这样做：

temp1->next = temp2;

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