天天看点

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

继续阅读