函數的聲明如下：

void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);??

分析：這是一道廣為流傳的Google面試題，能有效考察我們的編程基本功，還能考察我們的反應速度，更重要的是，還能考察我們對時間復雜度的理解。

在鏈表中刪除一個結點，最常規(guī)的做法是從鏈表的頭結點開始，順序查找要刪除的結點，找到之后再刪除。由于需要順序查找，時間復雜度自然就是O(n) 了。

我們之所以需要從頭結點開始查找要刪除的結點，是因為我們需要得到要刪除的結點的前面一個結點。我們試著換一種思路。我們可以從給定的結點得到它的下一個結點。這個時候我們實際刪除的是它的下一個結點，由于我們已經得到實際刪除的結點的前面一個結點，因此完全是可以實現的。當然，在刪除之前，我們需要需要把給定的結點的下一個結點的數據拷貝到給定的結點中。此時，時間復雜度為O(1)。

上面的思路還有一個問題：如果刪除的結點位于鏈表的尾部，沒有下一個結點，怎么辦？我們仍然從鏈表的頭結點開始，順便遍歷得到給定結點的前序結點，并完成刪除操作。這個時候時間復雜度是O(n)。那題目要求我們需要在O(1)時間完成刪除操作，我們的算法是不是不符合要求？實際上，假設鏈表總共有n個結點，我們的算法在n-1總情況下時間復雜度是O(1)，只有當給定的結點處于鏈表末尾的時候，時間復雜度為O(n)。那么平均時間復雜度[(n-1)*O(1)+O(n)]/n，仍然為O(1)。

#includeusing?namespace?std;

typedef?struct?LNode{
	int?data;
	LNode?*next;
}LNode,?*List;

void?InsertList(List?&l,?int?data)//頭插入節(jié)點
{
	List?head;
	LNode?*p=new?LNode;
	p->data=data;
	if(NULL==l)
		p->next=NULL;
	else
		p->next=l;
	l=p;
}

void?PrintList(List?l)//打印鏈表
{
	LNode?*p=l;
	while(p)
	{
		cout<data<<"?";
		p=p->next;
	}
	cout<next;
		delete?toBeDeleted?;
		l=p;		
	}
	else
	{
		if(toBeDeleted->next==NULL)//若刪除的節(jié)點時最后一個節(jié)點
		{
			p=l;
			while(p->next!=toBeDeleted)
				p=p->next;
			p->next=NULL;
			delete?toBeDeleted;
		}
		else//刪除節(jié)點時中間節(jié)點
		{
			p=toBeDeleted->next;
			toBeDeleted->data=p->data;
			toBeDeleted->next=p->next;
			delete?p;

		}

	}

}

void?main()
{
	List?l=NULL;
	LNode?*p;
	int?n;
	InsertList(l,?3);
	InsertList(l,?7);
	InsertList(l,?12);
	InsertList(l,?56);
	InsertList(l,?33);
	InsertList(l,?78);
	InsertList(l,?20);
	InsertList(l,?89);

	PrintList(l);
	cout<>n;

	p=l;
	while(p->data!=n?&&?p)
		p=p->next;

	if(!p)
	{
		cout<<"不存在這樣的節(jié)點！"<<endl;
		return;
	}
	else
		DeleteNode(l,?p);

	cout<<"刪除后的鏈表：";
	PrintList(l);



	

}