單鏈表的一些經(jīng)典面試題

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

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

  題目要求的是要刪除一個不是尾節(jié)點的節(jié)點，要刪除一個節(jié)點我們首先得知道是那個鏈表，是哪個節(jié)點節(jié)點，找到并且刪除它。所以我們設(shè)計的函數(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é)點，因為單鏈表只可以找到當(dāng)前結(jié)點的下一個節(jié)點。

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

  題目要求只遍歷一次就找到這個中間節(jié)點，可見按照我們的常規(guī)思路，先遍歷一遍計數(shù)節(jié)點的總個數(shù)，然后二遍遍歷直接找到節(jié)點是不行的。這就用到了單鏈表一個重要的概念——快慢指針。定義兩個指針slow和fast，slow指針每次往后走一個節(jié)點位置，fast指針每次往后走倆個節(jié)點位置，當(dāng)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)典題，我通過理解后和大家一起分享，希望對大家有些許幫助。