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

注意list中输入数据不需要声明数组

还有这些 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;

我的意思是 linked 列表 2 已正确 linked，您只需要 link 第一个列表的结尾与第二个列表的开头。

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

Trouble merging two linked lists in C

c

algorithm

merge

linked-list

singly-linked-list