涉及到链表的面试题:
- 如果有链表编号的参数,先明确链表的编号是从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");
}