C语言 使用虚拟节点连接 2 个单向链表

Question

一点背景信息，我们正在做这个庞大的项目，其中一部分是关于合并 2 个单向链表。链表的末端都有一个不同的虚拟节点，它的下一个字段指向前面的节点，这样我们就可以访问列表的尾部，并能够在 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 的虚拟节点也是如此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