题解 | #输出单向链表中倒数第k个结点#
输出单向链表中倒数第k个结点
http://www.nowcoder.com/practice/54404a78aec1435a81150f15f899417d
两个指针一个先走k步，一个后走，先走的到终点时后走的刚好到倒数第k个
/*输入一个单向链表，输出该链表中倒数第k个结点，
链表的倒数第1个结点为链表的尾指针。*/
#include<iostream>
using namespace std;
struct ListNode
{
int m_nKey;
ListNode* m_pNext;
};
void createlist_R(ListNode* &L,int n)//尾插法
{
L= new ListNode;
L->m_pNext=NULL;
ListNode *r=L;
for(int i=0;i<n;i++)
{
ListNode *p;
p=new ListNode;
cin>>p->m_nKey;
p->m_pNext=NULL;
r->m_pNext=p;
r=p;
}
}
void print(ListNode* L)
{
ListNode* p;
p=L->m_pNext;
while(p)
{
cout<<p->m_nKey<<" ";
p=p->m_pNext;
}
cout<<endl;
}
void kk(ListNode* &L,int k)
{
ListNode* a;
ListNode* b;
a=L->m_pNext;
b=L->m_pNext;
int i=0;
while((i<k)&&a)//a先向前走k步
{
a=a->m_pNext;
i++;
}
while(a&&b)//a到达终点时b到达倒数第k个顶点
{
a=a->m_pNext;
b=b->m_pNext;
}
cout<<b->m_nKey<<endl;
}
int main()
{
ListNode* L;
int n;
int k;
while(cin>>n)
{
createlist_R(L,n);
cin>>k;
// print(L);
if(k!=0) kk(L,k);
else cout<<0<<endl;
}
}
