單鏈表的一些經(jīng)典面試題-創(chuàng)新互聯(lián)

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

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

 （一）刪除一個非尾節(jié)點：

 題目要求的是要刪除一個不是尾節(jié)點的節(jié)點，要刪除一個節(jié)點我們首先得知道是那個鏈表，是哪個節(jié)點節(jié)點，找到并且刪除它。所以我們設計的函數(shù)是這樣的：

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

 其實實現(xiàn)起來也很簡單，主要思想是刪除pos位置的下一個節(jié)點，因為單鏈表只可以找到當前結(jié)點的下一個節(jié)點。

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

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

SListNode* FindMidNode(SListNode* pHead)//pHead是鏈表的頭節(jié)點
{
	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;
}

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

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

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

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

SListNode* WhetherRing(SListNode* pHead)//判斷是否帶環(huán)，若帶，返回相遇節(jié)點
{
	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é)點。然后從相遇節(jié)點處斷開帶環(huán)鏈表，一個指針從鏈表投節(jié)點處開始往后遍歷，一個指針從斷開處往后遍歷，相遇節(jié)點處就是環(huán)的入口點

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

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

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

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

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

廣告

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