合并 2 个单向链表（无头节点）

Question

我有 2 个单链表 没有头节点 :

列表 1：[x1->x2->.....->xn]

列表 2：[y1->y2->......->ym]

合并后：

如果(n < m)

列表 1：[x1->y1->x2->y2->.....->xn->yn->y(n+1)->....->ym]

其他

列表 1：[x1->y1->x2->y2->.....->xm->ym->x(m+1)->....->xn]

这是我的合并函数：

void merge(NODE *list1, NODE *list2)
{
    NODE *ptr1 = list1;
    NODE *ptr2 = list2;

    while(1)
    {
        if(ptr2 == NULL)
            break;

        if(ptr1->next == NULL)
        {
            ptr1->next = ptr2;
            display(list1);

            while(list2 != NULL)
                list2 = list2->next;

            break;
        }

        list2 = list2->next;

        ptr2->next = ptr1->next;
        ptr1->next = ptr2;

        ptr2 = list2;
        ptr1 = (ptr1->next)->next;

        display(list1);
    }
}

但是在main函数中执行后，LIST 2应该是空的，但不是。

例如：

列表 1：[1-> 2-> 3]

列表 2：[5->6->7]

合并后：

列表 1：[1-> 5-> 2-> 6-> 3-> 7]

列表 2：[5-> 2-> 6-> 3-> 7]（这应该是空的）

请解释！

编辑：

示例输出：

------------[列表 1]----------

输入一个元素（-123退出）：1

[列表：1]

输入一个元素（-123退出）：2

[ 列表：1 2 ]

输入一个元素（-123退出）：-123

------------[列表 2]----------

输入一个元素（-123退出）：5

[列表：5]

输入一个元素（-123退出）：6

[列表：5 6]

输入一个元素（-123退出）：7

[列表：5 6 7 ]

输入一个元素（-123退出）：8

[列表：5 6 7 8]

输入一个元素（-123退出）：-123

[列表：1 5 2]

[列表：1 5 2 6 7 8]

------------[合并列表]----------

[列表：1 5 2 6 7 8]

[列表：5 2 6 7 8]

Answer 1

没有理由List2为空：

列表 2 不是真正的列表，只是指向第二个列表的第一个元素的指针，合并后成为完整列表的第二个元素。

在内存中，只有一个列表[1->5->2-> 6-> 3-> 7]，指针list1指向它的第一个元素，list2指向第二个元素。

因此，当您打印 list1 时，它将打印从表 1 开始的列表，而当您打印 list2 时，它将打印从 5

开始的列表

Answer 2

指针就是指针。他们只是指着东西。有一个指向链表中间的指针是完全有效的。这样，一个列表可以是另一个列表的子集。正如评论中所指出的，这不是合并函数的奇怪行为。

但是，如果您想这样做：为了 "make list 2 empty" 你可以在调用后取消引用它。像这样：

merge(list1, list2);
list2 = NULL;

如果你想在函数内完成它，你可以使用指向指针的指针：

void merge(NODE **list1, NODE **list2)
{
    NODE *ptr1 = *list1;
    NODE *ptr2 = *list2;    
 // Do stuff
    if(blabla) 
        **list1 = NULL;
    else
        **list2 = NULL;
}

然后像这样调用合并：

merge(&list1, &list1)

合并 2 个单向链表（无头节点）

Merging 2 Singly Linked Lists (without Head Node)

c

merge

singly-linked-list