函數(shù)的聲明如下：

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

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

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

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

上面的思路還有一個問題：如果刪除的結(jié)點位于鏈表的尾部，沒有下一個結(jié)點，怎么辦？我們?nèi)匀粡逆湵淼念^結(jié)點開始，順便遍歷得到給定結(jié)點的前序結(jié)點，并完成刪除操作。這個時候時間復(fù)雜度是O(n)。那題目要求我們需要在O(1)時間完成刪除操作，我們的算法是不是不符合要求？實際上，假設(shè)鏈表總共有n個結(jié)點，我們的算法在n-1總情況下時間復(fù)雜度是O(1)，只有當(dāng)給定的結(jié)點處于鏈表末尾的時候，時間復(fù)雜度為O(n)。那么平均時間復(fù)雜度[(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);



	

}