剑指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");
}