單鏈表的一些經典面試題

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

  （一）刪除一個非尾節點：

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

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

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

（二）找到單鏈表的中間節點：

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

SListNode* FindMidNode(SListNode* pHead)//pHead是鏈表的頭節點
{
	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個節點，或者判斷鏈表是否帶環等等，下面會有列子。

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

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

  如果帶環，快慢指針一定會在某個節點處相遇。（fast一直在環里轉，總有一個時刻，slow追上fast，相遇）

SListNode* WhetherRing(SListNode* pHead)//判斷是否帶環，若帶，返回相遇節點
{
	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;//沒有環
		}
		if (fast == slow)
		{
			return slow;//有環
		}
	}
	return NULL;
}

  如果鏈表帶環的話，我們就可以求出相遇的節點。然后從相遇節點處斷開帶環鏈表，一個指針從鏈表投節點處開始往后遍歷，一個指針從斷開處往后遍歷，相遇節點處就是環的入口點

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

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