劍指offer刷題【13】

代碼的魯棒性

魯棒性是指程式能夠判斷輸入是否合乎規範要求，并對不符合要求的輸入予以合理的處理。

提高代碼魯棒性的有效途徑，進行防禦性程式設計。預見在什麼地方可能出現問題，并在這些可能出現的問題制定處理方式。

面試題22：在連結清單中倒數第k個節點

struct ListNode
{
	int  m_nValue;
	ListNode* m_pNext;
};
           

周遊一遍 實作 找到倒數第k個節點，設定兩個指針，第一個指針走k-1步停下，第二個指針從頭指針開始周遊，

ListNode* FindKthToTail(ListNode* pListHead,unsigned int k)
{

  	if(ListHead == nullptr||k==0)
  		return nullptr;
	ListNode *pAhead = pListHead;
	ListNode *pBehind = nullptr;

	for(unsigned int i =0;i<k;++i)
	{
		if(pAhead->m_pNext!= nullptr)
			pAhead = pAhead->m_pNext;
		else
		{
			return nullptr;
		}
	}
	pBehind = pListHead;
while(pAhead->m_pNext != nullptr)
{
	pAhead = pAhead->m_pNext;
	pBhind = pBehind->m_pNext;
}
	return pBehind;

}
           

代碼不夠魯棒

(1) 輸入pListNode 為空指針，由于代碼會試圖通路空指針指向的記憶體，進而造成程式崩潰

2）輸入的以pListHead 為節點的連結清單的節點數少于k，由于在for循環中會在連結清單上向前走k-1步，仍然會由于空指針而造成程式崩潰

3）輸入參數k為0。

面試題23：連結清單中環的入口節點

如果一個連結清單中包含環，如何找出環的入口節點？

ListNode* MeetingNode(ListNode* pHead)
{
	if(pHead == nullptr)
		return nullptr;
	ListNode* pSlow = pHead->m+pNext;
	if(pSlow == nullptr)
		return nullptr;
	
	ListNode* pFast = pSlow->m_pNext;
	while(pFast!= nullptr&&pSlow!= nullptr)
	{
		if(pFast == pSlow)
			return pFast;
		pSlow = pSlow->m_pNext;

		pFast = pFast->m_pNext;
		if(pFast != nullptr)
			pFast = pFast->m_pNext;
		
		
	}
	return nullptr;
}
           

ListNode* EntryNodeOfLoop(ListNode* pHead)
{
	ListNode(Node* meetingNode == MeetingNode(pHead));
	if(meetingNode == nullptr)
		return nullptr;
	
	int nodesInLoop =1;
	ListNode*pNode1 = meetingNode;
	while(pNode1->m_pNext!= meetingNode)
	{
		pNode1 = pNode1->m_pNext;
		++nodesInLoop;
	}

	pNode1 = pHead;
	for(int i =0;i<nodesInLoop;++i)
		pNode1 = pNode1->m_pNext;

	ListNode* pNode2 = pHead;

	while(pNode1 != pNode2)
	{
		pNode1 = pNode1->m_pNext;
		pNode2 = pNode2->m_pNext;
	}
	return pNode1;
}
           

反轉連結清單

定義一個函數，輸入一個連結清單的頭節點，反轉該連結清單并輸出反轉後連結清單的頭節點。連結清單的節點定義如下：

struct ListNode
{
	int m_nKey;
	ListNode *m_pNext;
}

ListNode* ReverseList(ListNode* pHead)
{
	ListNode* pReversedHead =nullptr;
	ListNode* pNode = pHead;
	ListNode* pPrev = nullptr;
	while(pNode != nullptr)
	{	
		ListNode* pNext = pNode->m_pNext;

		if(pNext == nullptr)
			pResversedHead = pNode;
		pNode->m_pNext = pPrev;

		pPrev = pNode;
		pNode = pNext;
		
	}
	return pReversedHead;
}

           

為了避免連結清單在節點i處斷裂，我們需要調整節點i的m_pNext之前，把節點j儲存下來。

面試題 ：合并兩個連結清單

輸入兩個遞增排序的連結清單，，合并這兩個連結清單并使新連結清單中的節點仍然是遞增排序的。

struct ListNode
{
	int m_nValue;
	ListNode* m_pNext;
}

ListNode* Merge(ListNode* pHead1,ListNode* pHead2)
{
	if(pHead1 == nullptr)
		return pHead2;
	else if(pHead2 == nullptr)
		return pHead1;
	
	ListNode* pMergeHead = nullptr;
	
	if(pHead1->m_nValue<pHead2->m_nValue)
	{
		pMergeHead = pHead1;
		pMergeHead->m_pNext = Merge(pHead1->m_pNext,pHead2)
		
	}
	else
	{
		pMergeHead = pHead2;
		pMergeHead->m_pNext = Merge(pHead1,pHead2->m_pNext);
		
	}
	return pMergeHead;
}
           

考察分析問題的能力，需要大量指針操作，分析哪些情況會引入空指針，并考慮怎麼處理這些空指針。

樹的子結構

輸入兩顆二叉樹A和B，判斷B是不是A的子結構，

struct BinaryTreeNode
{
	double  m_dbValue;
	BinaryTreeNode* m_pLeft;
	BinaryTreeNode* m_pRight;
};


bool HasSubtrr(BinaryTreeNode* pRoot1,BinaryTreeNode* pRoot2)
{
	bool result = false;
	
	if(pRoot1 != nullptr &&pRoot2!= nullptr)
	{
		if(Equal(pRoot1->m_dbVaule,pRoot2->m_dbValue))
			result = DoesTree1HaveTree2(pRoot1,pRoot2);
		if(!result)
			rsult = HasSubtree(pRoot1->m_pLeft,pRoot2);
		
		if(!result)
			result = HasSubtree(pRoot1->m_pRight,pRoot2);
	}
	return result;
}


bool DoseTree1HaveTree2(BinaryTreeNode* pRoot1,BinaryTreeNode* pRoot2)
{
	if(pRoot2 == nullptr)
		return true;
	if(pRoot1 == nullptr)
		return false;
	
	if(!Equal(pRoot1->m_dbValue,pRoot2->m_dbValue))
		return false;
	
	return DoseTree1HaveTree2(pRoot1->m_pLeft,pRoot2->m_pLeft)
			&&DoseTree1HaveTree2(pRoot1->m_pRight,pRoot2->m_pRight);
}


bool Equal(double num1,double num2)
{
	if((num1-num2>-0.00000001)&&(num1-num2<0.00000001))
		return true;
	else
		return false;
}
           

和連結清單相比，樹中的指針操作也更多也更複雜，