【剑指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:[e-mail]
**********************************/
#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。对一切“->”进行指诊检查，确保不发生内存错误。野指针是严重错误。
• 防御式编程，对输入參数为空进行推断。