第十三題
題目：輸入一個單向鏈表，輸出該鏈表中倒數第k個結點。
這道題比較簡單，就是對於這個鏈表，定義兩個指針head1 head2，然後讓head1向前走k-1個位置以後，head2和head1同時向前走，知道head1知道NULL指針，head2的即為倒數第k個指針。
代碼：
[cpp]
#include<iostream>
using namespace std;
typedef struct node
{
node * nodeNext;
int value;
}node;
int seekReListK(node *head, int k)
{
if(NULL==head)
{
cout<<"空鏈表";
return -1;
}
node *head1 = head;
node *head2 = head;
k = k - 1;
while(k)
{
k = k - 1;
if(NULL!=head1 ->nodeNext)
head1 = head1 ->nodeNext;
else
{
cout<<"K超過鏈表的長度"<<endl;
return -1;
}
}
//現在head1比head2快k個
while(NULL!=head1->nodeNext)
{
head1 = head1->nodeNext;
head2 = head2->nodeNext;
}
return head2->value;
}
int main()
{
//構建鏈表
node *a = new struct node();
node *b = new struct node();
node *c = new struct node();
node *d = new struct node();
node *e = new struct node();
node *f = new struct node();
node *g = new struct node();
node *h = new struct node();
node *i = new struct node();
node *j = new struct node();
a->nodeNext = b;
b->nodeNext = c;
c->nodeNext = d;
d->nodeNext = e;
e->nodeNext = f;
f->nodeNext = g;
g->nodeNext = h;
h->nodeNext = i;
i->nodeNext = j;
j->nodeNext = NULL;
a->value = 0;
b->value = 1;
c->value = 2;
d->value = 3;
e->value = 4;
f->value = 5;
g->value = 6;
h->value = 7;
i->value = 8;
j->value = 9;
cout<<seekReListK(a,1)<<endl;
cout<<seekReListK(a,10)<<endl;
cout<<seekReListK(a,11)<<endl;
return 0;
}
