链式有序表的合并中，为什么要把第二个表的头结点释放掉？

[jmyz0455]

在链式有序表的合并中，假设头指针为 LA 和 LB 的单链表分别为线性表 LA 和 LB 的存储结构，归并 LA 和 LB 得到单链表 LC 。

网上很多教材的算法描述里，最后都要把 LB 的头结点释放掉，就这一点我想不明白。请问：

1 、为什么要释放 LB 的头结点？

2 、那么释放掉头结点的线性表 LB 是不是就不存在了（被删掉）？

3 、如果 2 的答案是「是」，那么为什么合并线性表 LA 和 LB 之后要只剩下 LA 和 LC ？不应该是三个表都保留吗？

就是想不明白释放 LB 头结点是为了什么，可能我有些基础的概念遗漏了？请各位指点一下。

[Andiry]

取决于链表头是一个真实节点还是一个假节点。真实节点不释放。

[jmyz0455]

@Andiry 书上的例题，刚讲到线性表，完全没提到真假节点，就算是网上搜索也没有提到这个例题有没有真假节点的说法

[Kilerd]

取决于你的链表设计吧。

链表分好多种： 单纯链表，带表头的链表（为了统一算法），循环链表 blabla...一大堆

估计你看到的就是 带表头的链表 算法吧。

[mimzy]

我从直觉上去理解

1. 释放头结点就是为了该结点所占的空间，保证这个空间以后可以被其他的东西占用。
2. 只是头结点不存在了，头结点后面的结点该怎么连着还怎么连着，空间也占着。
3. LA 和 LC 最后变成了一个东西，就是合并后的链表。只不过 LC 直接利用了 LA 原来的头结点。

真实世界的情况可能未必是这样，但是国内数据结构的课程里应该是我说的这种情况。

[cfans1993]

没头结点的，初始时头和尾指针都指向 null

有头结点的，初始化时头和尾指针都指向头结点。一般头结点内不存储实际数据，作为标记用，如果头尾指针指向同一个结点说明为空；另外删除第一个节点时（头节点的下一个）不容易出错

回到题主的那个问题上，在合并过程中以 A 为基础，然后把 b 给合并到 a 当中，在合并过程中 a 和 b 的数据已经交叉在一起，也就是 a 中的数据节点已经有指向 b 中的， b 中的数据节点也要指向 a 中的， a 和 b 都已经完全脱离原来的形态， b 的那个头节点依然占着一个结点空间，把它删除也就相当于删除了这个已经没什么卵用的头结点

[cfans1993]

过一会儿给你上个图

[cfans1993]

大概是这个样子

[jmyz0455]

@cfans1993 非常感谢！一看就懂了，我在 CSDN 发两天了都没人回答，刚来 V2EX 就几个人回了，感谢大家，我以后有编程的问题都可以来着问吗，我看这个论坛聊别的也很多，数据结构的去什么论坛问人气多点？

[jmyz0455]

@mimzy 嗯嗯，七楼的图很直观，现在懂了，谢谢

[jmyz0455]

@Kilerd 看到七楼的图瞬间懂了，谢谢

[jmyz0455]

@cfans1993

[jmyz0455]

@cfans1993 @mimzy

书本里的代码是这样的，应该跟你们描述的情况一样吧，我怕说错了，注释没打：

void MergeList_L(LinkList &LA, LinkList &LB, LinkList &LC)
{
pa = LA->next; pb = LB->next;
LC = LA;
pc = LC;
while(pa && pb)
{
if(pa->data <= pb->data)
{
pc->next = pa;
pc = pa;
pa = pa->next;
}
else
{
pc->next = pb;
pc = pb;
pb = pb->next;
}
pc->next = pa ? pa : pb;
delete LB;
}
}

我自己也画了下图，的确是连起来的，稍微问一下既然 LB 都删了怎么 LA 还留着，好像就留 LC 足够了吧

[cfans1993]

我不知道你的链表是怎么实现的，不过成员数据主要是三项：头尾指针，加上一个头结点。删除一个链表时，会连带把他的头尾指针和头节点都删掉，由于 a 中的头节点已经被 c 占用（共享），所以不能直接删除。如果想断开 a 与链表的连接，把 la 指向 null 就好了

[cfans1993]

你删了 la 然后打印 lc 的元素试试

[mimzy]

@jmyz0455 楼上已经给出解释了。因为 LC 和 LA 都是变量名而已，它们指向的是同一个结点（ LC = LA; 这一句传的是地址，并没有创造出新的结点），所以如果你删了 LA 的话， LC 也就一并删除了。

问问题可以在 V2EX ，也可以试试 http://segmentfault.com/ 。

[jmyz0455]

@mimzy 明白，谢谢！

[jmyz0455]

@cfans1993 我一时犯迷糊了，洗把脸回来思路清晰了好多，现在清楚了，谢谢！