使用虚拟节点连接 2 个单链表

Question

一些背景信息，我们正在做这个巨大的项目，其中一部分是关于合并 2 个单链表。 这两个链表的末尾都有一个不同的虚拟节点，并且它的 next 字段指向之前的节点，这样我们就可以访问链表的尾部，并能够在 O(1) 时间内合并 2 个列表 我打印两个列表，然后尝试合并它们，但是当我打印合并列表时，我看到 2 个额外的数据，它们是地址，我无法找出原因。

List1 = 500,501,502,
List2 = 600,601,
List3 = 500,501,502,ADDRESS,ADRESS,600,601

该节点有一个 *next 字段和一个 int id 字段。所以 dummynode *next 显示 list1 的最后一个有效节点，list2 的 dummynode 也分别显示 Board[i].ptr 和 Board[k].ptr 是每个列表的起点

这是代码:

Board[i].dummynode->next->next = Board[k].ptr;
free(Board[i].dummynode);
Board[i].dummynode= Board[k].dummynode;
node * u = Board[i].ptr;

while(u!=Board[k].dummynode)
{
    printf("%d ",u->id);
    u = u->next;
}

Answer 1

我的猜测是 Board[i].dummynode->next 实际上并未指向 Board[i] 的尾部。在合并两个列表之前可以打印 Board[i].dummynode->next->id 吗？

如果我的猜测是正确的，那么您将从 i 的尾部遍历到旧的 i 虚拟节点，然后到指向的任何内容，然后到 k 的头部。

i0 -> i1 -> i2 -> i dummy -> random
k0 -> k1 -> k2 -> k dummy

变成了

i0 -> i1 -> i2 -> i dummy -> random -> k0 -> k1 -> k2 -> k dummy