今天在一本試題書上看到一些特別好的單鏈表面試題，大家都知道單鏈表容易在頭節(jié)點(diǎn)處進(jìn)行刪除，在尾節(jié)點(diǎn)處進(jìn)行插入，下面我們就來(lái)討論一下這些面試題：

成都創(chuàng)新互聯(lián)堅(jiān)信：善待客戶，將會(huì)成為終身客戶。我們能堅(jiān)持多年，是因?yàn)槲覀円恢笨芍档眯刨?。我們從不忽悠初訪客戶，我們用心做好本職工作，不忘初心，方得始終。10余年網(wǎng)站建設(shè)經(jīng)驗(yàn)成都創(chuàng)新互聯(lián)是成都老牌網(wǎng)站營(yíng)銷服務(wù)商,為您提供網(wǎng)站建設(shè)、成都網(wǎng)站設(shè)計(jì)、網(wǎng)站設(shè)計(jì)、成都h5網(wǎng)站建設(shè)、網(wǎng)站制作、成都品牌網(wǎng)站建設(shè)、小程序開發(fā)服務(wù),給眾多知名企業(yè)提供過(guò)好品質(zhì)的建站服務(wù)。

 （一）刪除一個(gè)非尾節(jié)點(diǎn)：

 題目要求的是要?jiǎng)h除一個(gè)不是尾節(jié)點(diǎn)的節(jié)點(diǎn)，要?jiǎng)h除一個(gè)節(jié)點(diǎn)我們首先得知道是那個(gè)鏈表，是哪個(gè)節(jié)點(diǎn)節(jié)點(diǎn)，找到并且刪除它。所以我們?cè)O(shè)計(jì)的函數(shù)是這樣的：

void DelNotTailNode(SListNode* pos)
{
	assert(pos);
	SListNode* del = pos->next;
	pos->data = del->data;
	pos->next = del->next;
	free(del);
	del = NULL;
}

 其實(shí)實(shí)現(xiàn)起來(lái)也很簡(jiǎn)單，主要思想是刪除pos位置的下一個(gè)節(jié)點(diǎn)，因?yàn)閱捂湵碇豢梢哉业疆?dāng)前結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)。

（二）找到單鏈表的中間節(jié)點(diǎn)：

題目要求只遍歷一次就找到這個(gè)中間節(jié)點(diǎn)，可見按照我們的常規(guī)思路，先遍歷一遍計(jì)數(shù)節(jié)點(diǎn)的總個(gè)數(shù)，然后二遍遍歷直接找到節(jié)點(diǎn)是不行的。這就用到了單鏈表一個(gè)重要的概念——快慢指針。定義兩個(gè)指針slow和fast，slow指針每次往后走一個(gè)節(jié)點(diǎn)位置，fast指針每次往后走倆個(gè)節(jié)點(diǎn)位置，當(dāng)fast指針走到尾節(jié)點(diǎn)時(shí)，slow指針剛剛好走到中間節(jié)點(diǎn)位置；

SListNode* FindMidNode(SListNode* pHead)//pHead是鏈表的頭節(jié)點(diǎn)
{
	SListNode* fast = pHead;
	SListNode* slow = pHead;
	while (fast->next)
	{
		slow = slow->next;
		fast = fast->next;
		if (fast->next)
		{
			fast = fast->next;
		}
		else
		{
			break;
		}
	}
	return slow;
}

利用快慢指針可以解決很多類似的問(wèn)題，比如找到單鏈表的第N個(gè)節(jié)點(diǎn)，或者判斷鏈表是否帶環(huán)等等，下面會(huì)有列子。

（三）判斷一個(gè)鏈表是否帶環(huán)，若帶返回環(huán)的入口點(diǎn)（較難）

上面已經(jīng)說(shuō)過(guò)，通過(guò)快慢指針可以找到單鏈表中的任何節(jié)點(diǎn)，這也是通過(guò)驗(yàn)證的。那么原理上也可以判斷鏈表是否帶環(huán)：

 如果帶環(huán)，快慢指針一定會(huì)在某個(gè)節(jié)點(diǎn)處相遇。（fast一直在環(huán)里轉(zhuǎn)，總有一個(gè)時(shí)刻，slow追上fast，相遇）

SListNode* WhetherRing(SListNode* pHead)//判斷是否帶環(huán)，若帶，返回相遇節(jié)點(diǎn)
{
	if (pHead == NULL||pHead->next == NULL)
		return NULL;
	SListNode* fast = pHead;
	SListNode* slow = pHead;
	while (fast)
	{
		slow = slow->next;
		fast = fast->next;
		if (fast)
		{
			fast = fast->next;
		}
		else
		{
			return NULL;//沒有環(huán)
		}
		if (fast == slow)
		{
			return slow;//有環(huán)
		}
	}
	return NULL;
}

  如果鏈表帶環(huán)的話，我們就可以求出相遇的節(jié)點(diǎn)。然后從相遇節(jié)點(diǎn)處斷開帶環(huán)鏈表，一個(gè)指針從鏈表投節(jié)點(diǎn)處開始往后遍歷，一個(gè)指針從斷開處往后遍歷，相遇節(jié)點(diǎn)處就是環(huán)的入口點(diǎn)

SListNode* GetEnterNode(SListNode*  pHead)//找到鏈表環(huán)入口節(jié)點(diǎn)在哪（重點(diǎn)）
{
	SListNode* start = pHead;
	SListNode* tmp = WhetherRing(pHead);
	while (start != tmp)
	{
		start = start->next;
		tmp = tmp->next;
	}
	return start;
}

 這就是單鏈表的一些面試經(jīng)典題，我通過(guò)理解后和大家一起分享，希望對(duì)大家有些許幫助。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

分享標(biāo)題：單鏈表的一些經(jīng)典面試題-創(chuàng)新互聯(lián)
標(biāo)題URL：http://chinadenli.net/article26/djggjg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供外貿(mào)建站、域名注冊(cè)、動(dòng)態(tài)網(wǎng)站、App開發(fā)、電子商務(wù)、網(wǎng)站改版

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)