[华为]输出单向链表中倒数第k个结点

liukaida

　　输入一个单向链表，输出该链表中倒数第k个结点，链表的倒数第1个结点为链表的尾指针。
　　链表结点定义如下：
　　struct ListNode
　　{
　　int       m_nKey;
　　ListNode* m_pNext;
　　};
　　详细描述：
　　接口说明
　　原型：
　　ListNode* FindKthToTail(ListNode* pListHead, unsignedint k);
　　输入参数：
　　ListNode* pListHead  单向链表
　　unsigned int k  倒数第k个结点
　　输出参数（指针指向的内存区域保证有效）：
　　无
　　返回值：
　　正常返回倒数第k个结点指针，异常返回空指针

输入描述:
　　输入说明
1 输入链表结点个数
2 输入链表的值
3 输入k的值

输出描述:
　　输出一个整数

输入例子:

8
1 2 3 4 5 6 7 8
4
输出例子:

5


//利用两个指针遍历找到链表的倒数第K个元素
#include<iostream>
using namespace std;
struct ListNode
{   
int val;   
ListNode* next;   
ListNode(int a)
{        
val=a;        
next=NULL;   
}
};

ListNode *findKth(ListNode *head,int k)
{   
if(k<1)        return NULL;   
ListNode *p1 = head;   
ListNode *p2 = head;   
for(int i = 0; i<k-1; i++)
{        
p1 = p1->next;   
}   
while(p1 !=NULL)
{        
p1 = p1->next;      
p2 = p2->next;   
}   
return p2;
}

int main()
{   
int n;   
while(cin>>n)
{        
int val;      
ListNode *head = new ListNode(0);        
ListNode *p = head;        
for(int i = 0; i<n; i++)      
{            
cin>>val;            
ListNode *q = new ListNode(val);            
p->next = q;            
p = p->next;      
}        
int k;        
cin>>k;        
ListNode *temp = findKth(head,k+1);//本题的特殊之处，存在倒数第0个        
cout<<temp->val<<endl;   
}   
return 0;
}