题目：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)的时间删除该节点。

struct ListNode
{
 int    m_nValue;
 ListNode* m_pNext;
};

void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted)；

算法思路：

一般我们是从头节点开始遍历，知道找到要删除的节点的前面一个节点，但是时间复杂度为O(n)
改进思路：找到要删除的节点pDeleteNode的下一个节点pNext，把下一个节点的值（pNext->m_nValue）
赋给要删除的节点(PDeleteNode->m_nValue),再把要删除的节点指向下一个节点的下一个节点：（pDelete->m_pNext = pNext->m_pNext）
然后再把pNext节点删除，pNext = NULL；

代码：

// DeleteNodeInList.cpp : 定义控制台应用程序的入口点。//#include "stdafx.h"#include<iostream>using namespace std;/*算法思路：一般我们是从头节点开始遍历，知道找到要删除的节点的前面一个节点，但是时间复杂度为O(n)改进思路：找到要删除的节点pDeleteNode的下一个节点pNext，把下一个节点的值（pNext->m_nValue）赋给要删除的节点(PDeleteNode->m_nValue),再把要删除的节点指向下一个节点的下一个节点：（pDelete->m_pNext = pNext->m_pNext）然后再把pNext节点删除，pNext = NULL；*/struct ListNode{	int		  m_nValue;	ListNode* m_pNext;};void DeleteNode(ListNode** pListHead, ListNode* pToBeDeleted){	if (!pListHead || !pToBeDeleted)	{		return;	}	if (pToBeDeleted->m_pNext != NULL)//删除的节点不是尾巴节点	{		ListNode* p = pToBeDeleted->m_pNext;		pToBeDeleted->m_nValue = http://www.mamicode.com/p->m_nValue;>

对于n-1个非尾巴节点而言，我们可以在O(1)的时间把下一个节点的内存复制覆盖要删除的节点，并删除下一个节点；
对于尾巴节点而言，由于仍然需要顺序查找，时间复杂度是O(n).因此总的平均时间复杂度是[(n-1)*O(1)+O(n)]/n,
因此平均时间复杂度是O(1);
 
 
在O(1)时间内删除链表节点