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

Question

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

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

节点有一个*next字段和一个int字段。接下来显示为list1的最后一个有效节点，list2的虚拟节点，Boardi.ptr和Boardk.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