剑指Offer之链表中倒数第k个结点

题目描述：

输入一个链表，输出该链表中倒数第k个结点。
(hint: 请务必使用链表。)

输入：

输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行为两个整数n和k(0<=n<=1000, 0<=k<=1000)：n代表将要输入的链表元素的个数,k代表要查询倒数第几个的元素。
输入的第二行包括n个数t(1<=t<=1000000)：代表链表中的元素。

输出：

对应每个测试案例，
若有结果，输出相应的查找结果。否则，输出NULL。

样例输入：

样例输出：

4
NULL

【解析】

剑指Offer之链表中倒数第k个结点

【代码】

/*********************************
*   日期：2013-11-20
*   作者：SJF0115
*   题号: 题目1517：链表中倒数第k个结点
*   来源：http://ac.jobdu.com/problem.php?pid=1517
*   结果：AC
*   来源：剑指Offer
*   总结：
**********************************/
#include<iostream>
#include <stdio.h>
#include <malloc.h>
#include <string.h>
using namespace std;

typedef struct ListNode{
    int value;
    struct ListNode *next;
}ListNode;

int FindKthToTail(ListNode*head,int k){
    //容错处理
    if(head == NULL || k <= 0){
        return NULL;
    }
    else{
        ListNode *p,*pre;
        //带头节点的链表
        pre = p = head->next;
        //第一个指针向前走k-1步，第二个指针保持不变
        for(int i = 0;i < k-1;i++){
            p = p->next;
        }
        //两个指针同时向前遍历
        while(p->next != NULL){
            pre = pre->next;
            p = p->next;
        }
        return pre->value;
    }
}

int main()
{
	int i,n,k;
	while(scanf("%d %d",&n,&k) != EOF){
	    ListNode *head,*p,*pre;
	    head = (ListNode*)malloc(sizeof(ListNode));
	    head->next = NULL;
        pre = head;
	    for(i = 0;i < n;i++){
	        p = (ListNode*)malloc(sizeof(ListNode));
	        scanf("%d",&p->value);
	        p->next = NULL;
            pre->next = p;
            pre = p;
	    }
	    //全部输出
	    if(n < k){
            printf("NULL\n");
	    }
	    else{
	        //倒数K个
            int num = FindKthToTail(head,k);
            if(num == NULL){
                printf("NULL\n");
            }
            else{
                printf("%d\n",num);
            }
	    }
	}
	return 0;
}

剑指Offer之链表中倒数第k个结点

相关推荐