給定鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針，在O(1)時(shí)間刪除該結(jié)點(diǎn)

題目：給定鏈表的頭指針和一個(gè)結(jié)點(diǎn)指針，在O(1)時(shí)間刪除該結(jié)點(diǎn)。

函數(shù)的聲明如下：
void DeleteNode(ListNode* pListHead, ListNode* pToBeDeleted);??

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

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

我們之所以需要從頭結(jié)點(diǎn)開始查找要?jiǎng)h除的結(jié)點(diǎn)，是因?yàn)槲覀冃枰玫揭獎(jiǎng)h除的結(jié)點(diǎn)的前面一個(gè)結(jié)點(diǎn)。我們?cè)囍鴵Q一種思路。我們可以從給定的結(jié)點(diǎn)得到它的下一個(gè)結(jié)點(diǎn)。這個(gè)時(shí)候我們實(shí)際刪除的是它的下一個(gè)結(jié)點(diǎn)，由于我們已經(jīng)得到實(shí)際刪除的結(jié)點(diǎn)的前面一個(gè)結(jié)點(diǎn)，因此完全是可以實(shí)現(xiàn)的。當(dāng)然，在刪除之前，我們需要需要把給定的結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)的數(shù)據(jù)拷貝到給定的結(jié)點(diǎn)中。此時(shí)，時(shí)間復(fù)雜度為O(1)。

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

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



	

}