3.4　从无头单链表中删除节点

假设有一个没有头指针的单链表。一个指针指向此单链表中间的一个节点（不是第一个，也不是最后一个节点），请将该节点从单链表中删除。

【解法一】

假设给定的指针为pCurrent，Node*pNext＝pCurrent→Next（pNext指向pCurrent所指节点的下一个节点）。

根据题意，pCurrent指向链表的某一个节点（除了最后一个节点），即pCurrent指向中间节点，那么此时pCurrent→Next≠NULL。

若pCurrent指向链表中间节点的某个节点B，如图3-5所示，则需要删掉B，使得A和C相连，如图3-6所示。删掉B容易，但是单链表节点并没有头指针，因此无法追朔到A，也就无法将A和C相连。

图3-5链表示意图

图3-6　删除之后链表示意图

重新考察所拥有的条件——尾指针，我们由pCurrent指向B，pNext（pCurrent→Next）指向C，同理pNext→Next（pCurrent→Next→Next）指向D，不过不能简单地删除B，因为那样会使得链表被分割。但是我们可以删除C，并通过pCurrent→Next＝pCurrent→Next→Next重新使链表连接，其中唯一丢失的是C中的data项。那么就让我们来上演一出算法版的“狸猫换太子”，将C中的数据取代B中的数据项，让B摇身一变成为C，然后将真正指向C的指针删除，这样我们就达到了目的，代码如下：

附完整代码：

代码清单3-7

扩展问题

编写一个函数，给定一个链表的头指针，要求只遍历一次，将单链表中的元素顺序反转过来。

总结

很多对C语言不熟悉的同学比较害怕指针的题目，其实指针不过是内存中的地址而已。在处理这类题目时，先画出清晰的图表会很有帮助。