【剑指Offer面试题】 九度OJ1517：链表中倒数第k个结点

鲁棒性是指程序可以推断输入是否符合规范要求，并对不和要求的输入予以 合理的处理。

题目链接地址：

http://ac.jobdu.com/problem.php?pid=1517

题目1517：链表中倒数第k个结点

时间限制：1 秒内存限制：128 兆特殊判题：否提交：2159解决：958

题目描写叙述：

输入一个链表，输出该链表中倒数第k个结点。

(hint: 请务必使用链表。)

输入：

输入可能包括多个測试例子。输入以EOF结束。

对于每一个測试案例。输入的第一行为两个整数n和k(0<=n<=1000, 0<=k<=1000)：n代表将要输入的链表元素的个数,k代表要查询倒数第几个的元素。

输入的第二行包括n个数t(1<=t<=1000000)：代表链表中的元素。

输出：

相应每一个測试案例，

若有结果，输出相应的查找结果。否则，输出NULL。

例子输入：

5 2

1 2 3 4 5

1 0

5

例子输出：

4

NULL

思路分析：

考察鲁棒性。

给定一个单向链表，找出倒数第k个节点并输出节点值。可以先让一个指针p1从链表头開始跑k歩，然后指针p2指向链表头。两指针同步向前走，当p1走到NULL时，p2即指向倒数第k点。

鲁棒检查：检查指针是否指向NULL，确保不发生内存错误。

代码：

/*********************************
【剑指Offer面试题】 九度OJ1517：链表中倒数第k个结点
Author:牧之丶 Date：2015年
Email:bzhou84@163.com
**********************************/
#include<stdio.h>
#include<stdlib.h>
#include<string>
#include <math.h>
#include<stack>
#include <vector>
#include <iostream>
using namespace std;typedef struct Node
{
int data;
struct Node *pNext;
}LNode;/*
找到单链表中倒数第k个元素
*/
LNode* FindKthToLast(LNode* pHead,unsigned int k)
{
if(pHead==NULL || k==0)
return NULL;
LNode* Head = pHead;
LNode* Behind = pHead;
for (unsigned int i=0;i<k-1;++i)
{
if (Head->pNext!=NULL)
{
Head=Head->pNext;
}
else
{
return NULL;
}
}
while (Head->pNext!=NULL)
{
Head=Head->pNext;
Behind=Behind->pNext;
}
return Behind;
}int main()
{
int n,k;
while(scanf("%d %d",&n,&k) != EOF)
{
int i,data;
scanf("%d",&data);
LNode* pHead =(LNode*)malloc(sizeof(LNode));
if(pHead == NULL)
exit(EXIT_FAILURE);
pHead->data = data;
pHead->pNext = NULL; LNode* pCur = pHead;
for(i=0;i<n-1;i++)
{
scanf("%d",&data);
LNode* pNew =(LNode* )malloc(sizeof(LNode));
if(pNew == NULL)
exit(EXIT_FAILURE);
pNew->data = data;
pNew->pNext = NULL;
pCur->pNext = pNew;
pCur = pCur->pNext;
} LNode* pFind = FindKthToLast(pHead,k);
if(pFind == NULL)
printf("NULL\n");
else
printf("%d\n",pFind->data);
}
return 0;
}/**************************************************************
Problem: 1517
Language: C++
Result: Accepted
Time:100 ms
Memory:3104 kb
****************************************************************/


总结

• 善用两个指针遍历链表解决遇到的问题
• 检查指针是否指向NULL。对一切“->”进行指诊检查，确保不发生内存错误。野指针是严重错误。
• 防御式编程，对输入參数为空进行推断。