【题目】
输入一个链表，输出该链表中倒数第k个结点。
【分析】
对于此题。考虑单链表实现，单链表仅仅能从头到尾遍历，而要找到倒数第k个结点，就须要确定，正数是第几个结点，假设结点总数为n。最后一个结点位置为n-1，而倒数第k个结点的位置就为n-k+1。假设从头节点開始遍历，仅仅要遍历到n-k+1步就能够。这就意味着我们须要知道两个关键信息，一个是链表长度，一个就是n-k+1。这就须要遍历两次。非常明显，这不是最佳方案。比較好的方法就是一次遍历就能够找到，假设我们用两个指针，当一个指针指向n，还有一个指针和他相距k-1个时。还有一个指针所指向的位置就是n-k+1的位置。就是我们要找的位置，利用两个间距为k-1的指针实现此题不失为一种有效的办法。
【測试代码】
#include<stdio.h>
#include<stdlib.h>
#include<stack>
typedef int data_type;
typedef struct Node node_t;// 给struct Node取个别名node_t
typedef struct Node * node_ptr;//给struct Node*取个别名node_ptr
typedef struct Node
{
data_type data;
struct Node *node_next;//node_next是一个指向结构的指针，告诉指针要指向的地址就要付给它一个结构类型地址
};
//链表初始化
node_t * init()
{
node_ptr p;
p = (node_t *)malloc(sizeof(node_t));
p->node_next = NULL;
return p;
}
//在链表后面插入结点
node_t *insert_back(node_ptr p , data_type data)
{
node_ptr pnew = (node_t *)malloc(sizeof(node_t));
pnew ->node_next = NULL;
pnew ->data = data;
p->node_next = pnew;
return pnew;
}
node_t * find(node_ptr p, unsigned int k)
{
if(p == NULL || k == 0)
return NULL;
node_ptr pAhead = p;
node_ptr pBehind =NULL;
for( int i = 0 ; i<k-1; i++)
{
if(pAhead->node_next != NULL)
pAhead = pAhead->node_next;
else
return NULL;
}
pBehind = p;
while(pAhead->node_next != NULL)
{
pAhead = pAhead->node_next;
pBehind = pBehind->node_next;
}
return pBehind;
}
//正常打印
void print(node_ptr p)
{
if(!p)
{
printf("no data, you think too much");
return ;
}
while(p->node_next != NULL)
{
printf("%d ", p->data);
p = p->node_next;
}
printf("%d ", p->data);
printf("
");
}
void main()
{
node_ptr pnode, list;
pnode = init();
list = pnode;
pnode = insert_back(pnode, 1);
pnode = insert_back(pnode, 2);
pnode = insert_back(pnode, 3);
pnode = insert_back(pnode, 4);
pnode = insert_back(pnode, 5);
pnode = insert_back(pnode, 6);
node_t *target = find(list, 3);
int find_data = target->data;
printf("倒数第3个数是：%d
",find_data);
}这里一定要注意一些特殊条件。假设单链表是空的，查找的位置设定为0，结点总数小于k。这些都是要考虑的，否则一旦出现这样的測试问题。整个程序都会崩溃，小漏洞是能够使整个功亏一篑的。
【输出】
【延伸】
这个题解题思路能够延伸到其它须要遍历測试的，比方说測试一个单链表是不是回环。设置两个指针。一个指针一次一步。还有一个一次两步。到最后假设快的指针居然追上了慢的那个就说明，是回环。假设走得快的走到了链表的末尾还是没有追上慢的说明，不是回环；还有測试单链表的中间结点，设置两个指针。一个走一步。还有一个走两步。走两步的走到末尾时，走得慢的就走到了中间节点处，由于快的指针是慢的2倍，快的走到了n-1位置。慢的位置就是(n-1)/2，这样的一个指针不能一次性遍历解决这个问题的就用两个指针。