劍指offer 連結清單與指針

涉及到連結清單的面試題：

• 如果有連結清單編号的參數，先明确連結清單的編号是從0開始還是從1開始
• 如果輸入有編号、個數這樣的參數時，使用unsigned int ，這樣最多隻需要判斷其不等于0即可
• 兩個指針可以做很多事，例如先把他們間隔固定，最後一個到結尾時，第一個指針就指向倒數第n個結點了
• 輸入的有效性必須進行判斷，涉及到魯棒性
• 在代碼中，有Node->Next_Node出現時，注意判斷其是否為NULL（nullptr）
• 當一個指針在連結清單上不能解決問題時，我們可以用兩個指針（讓一個走得快（兩步），一個走一步），這可以解決找到連結清單中間節點的問題

#include <iostream>  
#include <string>  
#include <vector>  
#include <stack>
using namespace std;  

typedef int datatype;

struct Node
{
	datatype value;
	Node* Next_Node;
};

//從頭到尾列印連結清單中的結點
/*面試官是否允許這個函數允許改變輸入，也就是改變輸傳入連結表的順序是一個交流點*/
bool Print_Node(Node **first)
{
	if (first == NULL || *first == NULL)
	{
		return false;
	}

	Node *Node_temp = *first;
	vector<Node*> My_Nodes;
	//利用棧的先進後出的特點也是比較好的
	stack <Node*> My_Nodes2;

 	while (Node_temp != NULL)
	{
		My_Nodes.push_back(Node_temp);
		My_Nodes2.push(Node_temp);//進
		Node_temp = Node_temp->Next_Node;
	}

	vector<Node*>::iterator it1 = My_Nodes.end();
	for (it1;it1 != My_Nodes.begin();it1--)
	{
		cout<<(*it1)->value<<endl;
	}

	while (!My_Nodes2.empty())
	{
		Node_temp = My_Nodes2.top();//出,棧頂元素指派
		cout<<Node_temp->value<<endl;
		My_Nodes2.pop();
	}
}

//找到一個連結清單中倒數第K個結點(正數就比較簡單了)
//與面試官交流，确認尾結點的編号(0或1皆可，這裡取第一個結點的編号為1)(輸入為unsigned比較重要“編号類的題目”)(或者int的話，就 <= 0)
//兩種方法：1 先周遊找到結點個數，再周遊 2：兩個指針，第一個指針先走k-1步，然後第二個指針指向首指針，最後第一個指針走到最後，第二個指針就指向倒數第k個結點
Node* Find_k(Node** first, unsigned int k)
{
	if (first == NULL || *first == NULL || k == 0)
	{
		return NULL;
	}

	Node* Node_temp = *first;
	for(int i = 0;i<k-1;i++)
	{
		if (Node_temp->Next_Node != NULL)
		{
			Node_temp = Node_temp->Next_Node;
		}
		else
		{
			return NULL;
		}	
	}

	Node* Node_temp2 = *first;
	while (Node_temp != NULL)
	{
		Node_temp = Node_temp->Next_Node;
		Node_temp2 = Node_temp2->Next_Node;
	}
	return Node_temp2;
}

void main()  
{     

	system("pause");
}