O(1)时间下删除链表的结点

在给定单向链表的头指针和一个结点指针，定义一个函数在O（1）时间内删除该结点。链表的结点结构如下：

typedef int ElemType; 
typedef struct Node 
{
	ElemType data;
	struct Node *next; 
}PointList;

在单链表中删除一个结点，常规的做法无疑是从链表的头节点开始，顺序遍历查找要删除的结点，并在链表中删除该结点。

如上图所示的链表中，我们想删除结点i，可以从链表的头结点开始顺序遍历，发现h的next指向要删除的结点i，于是我们可以把结点h的next结点指向i的next，即结点j。指针调整后我们就可以安全的删除结点i并保证链表没有断开。
之所以需要从头开始查找，是因为我们需要得到将要删除结点的前一个结点。
在单向链表中，结点中没有指向前一个结点的指针，所以只好从链表的头结点开始顺序查找。

那是不是一定需要得到删除结点的前一个结点呢？
答案是否定的。在单链表中，我们可以很方便的得到要删除节点的下一个结点。如果我们把下一个结点的内容复制到需要删除的结点上，覆盖原有的内容，在把下个结点删除，那是不是相当于把当前需要删除的结点删除了？

按照上述思路，，我们要删除结点i，先把i的下个结点j的内容复制到i，然后把i的指针指向结点j的下一结点。此时再删除结点j，其效果刚好是把结点i删除了。

但是上述的思路有一个漏洞，如果删除的结点位于链表的尾部，那么它就没有下一个结点。我们仍然需要从链表的头节点开始，找到它的前序结点。

需要注意，如果链表中只有一个结点，那么我们在删除结点之后，还需要把链表的头指针置空。

下面是这种思路的参考代码：

void DeleteNode(PointList** head, PointList* node)
{
	if (!head || !node)
		return;

	if (node->next != NULL)
	{
		PointList* pNext = node->next;
		node->data = pNext->data;
		node->next = pNext->next;

		free(pNext);
		pNext = NULL;
	}
	else if (node == *head)
	{
		free(node);
		node = NULL;
		*head = NULL;
	}
	else {
		DeleteTail(head);
	}
}

接下来我们分析这种思路的时间复杂度。
对于n-1个非尾结点而言，我们可以在O(1)时间内把下一结点的内存复制覆盖要删除的结点，并删除下一结点；而对于尾结点而言，由于仍需顺序查找，时间发杂度是O(n)。因此，总的平均时间复杂度是[(n-1)*O(1)+O(n)]/n，结果还是O(1)，符合O(1)时间复杂度的要求。

值得注意的是，上述的代码是建立在要删除的结点的确在链表中的情况下。
我们需要O(n)的时间才能判断链表中是否包含某一结点。受到O(1)时间复杂度的限制，我们不得不把确保结点在链表中的责任推给了函数的调用者。

测试代码的结构头文件及实现来自：头指针单链表的C语言代码实现