- 题目描述:
- 输入一个链表,输出该链表中倒数第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; }