16:链表中倒数第k个结点

面试题16

题目描述：

输入一个链表，输出该链表中倒数第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-1。那么按照这样再继续遍历。当二个指针指向链表尾部时，就是第倒数第k个结点。需要考虑k=0，和链表为空的情况。

/* ***********************************************
Author        :bo-jwolf
Created Time  :2015年02月11日 星期三 21:50:17
File Name     :1517.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
struct ListNode{
	int m_nValue;
	ListNode* m_pNext;
};

ListNode* FindKthToTail( ListNode *pListHead, unsigned int k ){
	if( pListHead == NULL ?? k == 0 )
		return NULL;
	ListNode *pAhead = pListHead;
	ListNode *pBehind = NULL;
	for( unsigned int i = 1; i <= k - 1; ++i ){
		if( pAhead -> m_pNext != NULL ){
			pAhead = pAhead -> m_pNext;
		}
		else
			return NULL;
	}
	pBehind = pListHead;
	while( pAhead -> m_pNext != NULL ){
		pAhead = pAhead -> m_pNext;
		pBehind = pBehind ->m_pNext;
	}
	return pBehind;
}

int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
  	int n, k, temp;
  	while( scanf( "%d%d", &n, &k ) != EOF ){
		ListNode *head = NULL;
		ListNode *p = NULL;
		p = new ListNode;
		p ->m_pNext = NULL;
		head = p;
		for( int i = 1; i <= n; ++i ){
			ListNode *q = NULL;
			q = new ListNode;
			scanf( "%d", &temp );
			q -> m_nValue = temp;
		    q -> m_pNext = p -> m_pNext;
			p -> m_pNext = q;
			p = p ->m_pNext;
		}
		ListNode *t = FindKthToTail( head ->m_pNext, k );
		if( t != NULL )
			printf( "%d\n", t -> m_nValue );
		else
			puts("NULL");
	}
    return 0;
}

第二种方法，使用栈，根据栈的性质，先入后出，那么直接弹出k次，就可以得到相应值。需要注意的同上，其次就是当n<k。

/* ***********************************************
Author        :bo-jwolf
Created Time  :2015年02月11日 星期三 22:18:16
File Name     :1517a.cpp
************************************************ */

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
#include<stack>
using namespace std;
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
   	stack<int>Q;
   	int n, k, temp;
	while( scanf( "%d%d", &n, &k ) != EOF ){
		while( !Q.empty() ){
			Q.pop();
		}
		for( int i = 1; i <= n; ++i ){	
			scanf( "%d", &temp );
			Q.push( temp );
		}
		if( Q.empty() or k == 0 or n < k ){
			puts("NULL");
		}
		else{
			while( k-- ){
				temp = Q.top();
				Q.pop();
			}
			printf( "%d\n", temp );
		}
	}
    return 0;
}