目录
一、思路
二、代码
三、测试
四、总结
一、思路
设置两个指针，一个快指针，一个慢指针。快指针初始值指向第一个结点，慢指针则指向空
顾名思义，快指针先出发，等到快指针到达k-1位置时，令慢指针指向第一个结点，然后慢指针和快指针一起出发
等到快指针到达尾结点，此时，慢指针正好到达倒数第K个结点。
至于为什么是K-1，而不是K。我们看证明，证明如下：
设链表长度为1，k = 1, y=k-1,那么y =0,也就是说快指针从第一个结点出发，令慢指针指向第一个结点，否则当快结点到达尾结点时，慢指针不会到达尾结点，即倒数第一个结点。快指针发现下一个结点为空，两个指针都停止前进，然后返回慢指针。此时慢指针刚好指向第一个结点。
设 链表长度为5，k = 5,y=k-1=4,此时快指针到达第五个结点，令慢指针指向第一个结点，然后慢指针和快指针一起出发，但是快指针发现此时已经到尾结点，因为一共五个结点，所以双方都停止前进，返回慢指针，倒数第五个，其实就是第一个。
二、代码
#include<iostream>
#include "malloc.h"
using namespace std;
typedef struct LNode {
int data;
struct LNode * next;
}LNode, *LinkList ;
int tail_create_heahLinked_List(LinkList & L,int n)
{
LinkList head = (LinkList)malloc(sizeof(LNode));//头结点的存储地址
if(NULL == head) return 1; //分配空间失败
L = head; //头指针L存储头结点P的地址，即头指针指向头结点
L->data = 0; //用头结点统计元素个数，刚开始为0个
L->next = NULL; //此时链表为空
LinkList temp = L;
for(int i = 0;i<n;i++)
{
LinkList List_Node = (LinkList)malloc(sizeof(LNode));
scanf("%d",&List_Node->data);
L->data++;
List_Node->next = NULL; //每插入一个元素，头结点统计链表元素个数加一
temp->next = List_Node; //尾插法，即链表中的元素顺序与输入相同
temp = temp->next;
if(i == n-1 ){
temp->next = NULL;
}
}
return 0;
}
LinkList Found_K_node(LinkList L,int k)
{
if( NULL == L || NULL == L->next || L->data < k || L->data == 0)
return NULL;
if( k == L->data)
return L->next;
if( k < 1)
return L->next;
LinkList front_Node = L->next;
LinkList later_Node = NULL;
for(int index = 0;index < k - 1;index++)
{
front_Node = front_Node->next;
}
later_Node = L->next;
while(front_Node->next != NULL)
{
front_Node = front_Node->next;
later_Node = later_Node->next;
}
return later_Node;
}
void headlinked_List_Traverse(LinkList L)
{
cout<<"该链表的元素个数为:"<<L->data<<endl;
LinkList p = L->next;
while(p)
{
cout<<p->data<<" ";
p = p->next;
}
cout<<endl;
}
int main()
{
int num;
int k;
cin>>num;
LinkList L =NULL;
if(!tail_create_heahLinked_List(L,num))
{
headlinked_List_Traverse(L);//打印链表
LinkList k_node =NULL;
while(cin>>k)
{
k_node = Found_K_node(L,k);
if(NULL != k_node)
cout<<"倒数第"<<k<<"个结点值为:"<<k_node->data<<endl;
else
cout<<"没有此结点"<<endl;
k = 0,k_node = NULL;
}
}
return 0;
}
三、测试
我们规定当K为负数时始终显示第一个结点值
5
1 2 3 4 5
该链表的元素个数为:5
1 2 3 4 5
1
倒数第1个结点值为:5
2
倒数第2个结点值为:4
3
倒数第3个结点值为:3
4
倒数第4个结点值为:2
5
倒数第5个结点值为:1
6
没有此结点
0
倒数第0个结点值为:1
-1
倒数第-1个结点值为:1
-100
倒数第-100个结点值为:1
四、总结
快慢指针是一个很有用的办法，特别是关于位置的操作，多加练习
另外要考虑程序的健壮性，考虑一些非法的操作，我们的程序不应该崩溃，而是给出合理的答案。
