刚开始，我想到的是一种笨方法，先遍历单链表，计算出单链表的长度len，然后再从头遍历单链表到第len-k个节点，那么
这个节点既是单链表的倒数第k个节点。
不过这种算法时间复杂度挺高的，还有一种更简单的方法，就是设置两个指针，分别指向单链表的头节点，然后让其中一个指针，先走k步，
之后，再让两个指针同时走，直到第一个指针走到单链表尾节点结束。
那么，第二个指针所指向的节点，就是倒数第k个节点。
代码如下：
#include <iostream>
#include <cstdlib> using namespace std; typedef struct list{
int data;
struct list *next;
}list_node,*listNode; void createList(listNode &list,int arr[],int n)
{
int i;
listNode temp;
for(i=0;i<n;i++)
{
temp=(list_node*)malloc(sizeof(list_node)); //为节点分配内存
if(temp)
{
temp->data=arr[i];
temp->next=NULL;
temp->next=list->next;
list->next=temp;
}
else
{
cout<<"内存分配失败"<<endl;
} }
}
/**
查找倒数第k个节点
*/
int find_knode(listNode list,int k)
{
if(list==NULL||k<0)
{
cout<<"链表不能为空或k值不能小于0"<<endl;
return 0;
}
listNode first;
listNode second;
int i=0;
first=list->next;
second=list->next;
while(i<k)
{
first=first->next;
i++;
}
if(first==NULL)
{
cout<<"链表长度小于k"<<endl;
return -1;
}
while(first)
{
first=first->next;
second=second->next;
}
return second->data; }
void show_list(listNode list)
{
listNode temp;
temp=list;
while(temp)
{
cout<<temp->data<<"---";
temp=temp->next;
}
} int main(){
int arr[]={12,3,6,1,9,17,19,21,22,87};
listNode list=NULL;
list=(list_node*)malloc(sizeof(listNode));
list->data=0;
list->next=NULL;
int k=6; int val;
cout<<"创建链表:"<<endl;
createList(list,arr,10);
val=find_knode(list,k);
cout<<"倒数第<<k<<个节点为:"<<val<<endl;
cout<<"show list:"<<endl;
show_list(list);
return 0; }
运行结果如下:
在运行sublime text2时发现出现 error2的错误。
解决办法如下：打开F:\SublimeText2\Data\Packages\C++\c++.sublime-build
{
"cmd": ["g++", "${file}", "-o", "${file_path}/${file_base_name}"],
"file_regex": "^(..[^:]*):([0-9]+):?([0-9]+)?:? (.*)$",
"working_dir": "${file_path}",
"selector": "source.c, source.c++",
"variants":
[
{
"name": "Run",
//"cmd": ["bash", "-c", "g++ '${file}' -o '${file_path}/${file_base_name}' && '${file_path}/${file_base_name}'"]
"cmd": [ "${file_path}/${file_base_name}.exe"]
}
]
}
看到有注释的那一行，是原先配置的，现在把它注释掉，添加下面的一行：
"cmd": [ "${file_path}/${file_base_name}.exe"]
重新运行，就可以了。