【摘要】：可以分如下两种情况来分析：如果这个结点是链表的最后一个结点，那么无法删除这个结点。如果这个结点不是链表的最后一个结点，可以通过把其后继结点的数据复制到当前结点中，然后删除后继结点的方法来实现。
【出自XM笔试题】
难度系数：★★★★☆ 被考察系数：★★★★☆
题目描述：
假设给定链表1-＞2-＞3-＞4-＞5-＞6-＞7中指向第5个元素的指针，要求把结点5删掉，删除后链表变为1-＞2-＞3-＞4-＞6-＞7。
分析与解答：
一般而言，要删除单链表中的一个结点p，首先需要找到结点p的前驱结点pre，然后通过pre.next=p.next来实现对结点p的删除。对于本题而言，由于无法获取到结点p的前驱结点，因此，不能采用这种传统的方法。
那么如何解决这个问题呢？可以分如下两种情况来分析：
（1）如果这个结点是链表的最后一个结点，那么无法删除这个结点。
（2）如果这个结点不是链表的最后一个结点，可以通过把其后继结点的数据复制到当前结点中，然后删除后继结点的方法来实现。实现方法如下图所示：
在上图中，第（1）步把结点p的后继结点的数据复制到结点p的数据域中；第（2）步把结点p的后继结点删除。实现代码如下：(www.xing528.com)
程序的运行结果如下：
删除结点5前链表：1 2 3 4 5 6 7
删除该结点后链表：1 2 3 4 6 7
算法性能分析：
由于这种方法不需要遍历链表，只需要完成一个数据复制与结点删除的操作，因此，时间复杂度为O（1）。由于这种方法只用了常数个额外指针变量，因此，空间复杂度也为O（1）。
引申：只给定单链表中某个结点p（非空结点），如何在p前面插入一个结点
分析与解答：
主要思路：首先分配一个新结点q，把结点q插入在结点p后，然后把p的数据域复制到结点q的数据域中，最后把结点p的数据域设置为待插入的值。
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
