数据结构-输出单链表倒数第K个结点值

【问题描述】输入一个单向链表，输出该链表中倒数第k个结点，链表的最后一个结点是倒数第1个节点。

【输入形式】输入第一位为K值，其后接一串以空格分隔的整型值，输入-1时停止建立链表。
【输出形式】输出为倒数第K个结点的值，若无，则输出Not Found

【样例输入】3 13 45 54 32 1 4 98 2 -1
【样例输出】4
【样例说明】K值为3，则输出链表倒数第3个结点的值，为4；数据输入间以空格隔开
 

//Drink
#include<iostream>
using namespace std;
template<class T>
struct LinkNode
{
	T data;				//数据域 
	LinkNode<T> *link;	//指针域 
	LinkNode(LinkNode<T> *ptr=NULL)
	{
		link = ptr;		//仅初始化指针成员的构造函数	
	}
	LinkNode(const T &item,LinkNode<T> *ptr=NULL)
	{
		link = ptr;		//初始化指针成员和数据的构造函数 
		data = item;
	}
}; 
template<class T>
class List
{
	protected: LinkNode<T> *first;			
	
	public: 
		List(){first = new LinkNode<T>;};	//构造函数创建空的单链表，并创建first 
		void inputRear(T endTag);			//endTag为结束标志 
		void output();
		void reout(int k); 					//输出单链表倒数第k个结点值 
};
template<class T>
void List<T>::inputRear(T endTag)
{	
	
	LinkNode<T> *newNode;
	LinkNode<T> *last;
	T val;
	cin>>val;
	last = first;	
	while(val != endTag)
	{
	
		newNode = new LinkNode<T>(val); //创建一个结点空间，新结点值为val 地址在newNode中 
		last->link = newNode;	//将新结点连接到表尾 

		last = newNode;			//新链表表尾变为地址变为newNode
		cin>>val;				//输入下一个结点得值 
	
	}
	last->link=NULL; 
}
template<class T>
void List<T>::reout(int k)
{
	LinkNode<T> *current=first->link;			//工作指针指向第一个带值结点 
	LinkNode<T> *r=first->link;					//再创建一个工作指针r 
	int count=0;								//current在带头结点处指向第一个结点
                                                //所以count=0 
												//current目的为遍历整个链表
												//r与current指针间隔k个结点
                                                //当current遍历结束后r刚好指向第k个结点	
	while(current!=NULL)
	{		
		current = current->link;				
		count++;
		if(count>k)				                //相隔距离为k+1才能输出第k个位置的结点； 
		r =r->link; 
	}

	if(count<k||r==NULL)		               //当链表结点个数小于相隔距离时输出notFind
								               //当r为空时也输出notFind 
	cout<<"Not Found"<<endl;
	else
    cout<<r->data<<endl;
}
int main()
{
	int k;
	cin>>k;
	List<int> l;
	l.inputRear(-1);
	l.reout(k);
	
return 0;

}