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

Question

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

我的想法是首先将指针指向第一个列表的末尾，然后做一个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

你的问题之一是：

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

您没有更新temp1的值。

还有，你为什么不在做以下事情的同时，代替这一秒：

temp1->next = temp2;

我的意思是链接列表2是正确链接的，你只需要把第一个列表的结尾和第二个列表的开头链接起来。

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

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

还有这些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都未初始化。