1.10 如何在只给定单链表中某个结点的指针的情况下删除该结点

【出自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）如果这个结点不是链表的最后一个结点，可以通过把其后继结点的数据复制到当前结点中，然后用删除后继结点的方法来实现。实现方法如下图所示。

在上图中，第一步首先把结点p的后继结点的数据复制到结点p的数据域中；第二步把结点p的后继结点删除。实现代码如下：

程序的运行结果为

算法性能分析：

由于这种方法不需要遍历链表，只需要完成一个数据复制与结点删除的操作，因此，时间复杂度为O（1）。由于这种方法只用了常数个额外指针变量，因此，空间复杂度也为O（1）。

引申：只给定单链表中某个结点p（非空结点），如何在p前面插入一个结点。

分析与解答：

主要思路：首先分配一个新结点q，把结点q插入到结点p后，然后把p的数据域复制到结点q的数据域中，最后把结点p的数据域设置为待插入的值。