微软等数据结构与算法面试100题 第十三题
第十三题
题目：输入一个单向链表，输出该链表中倒数第k个结点。
这道题比较简单，就是对于这个链表，定义两个指针head1 head2，然后让head1向前走k-1个位置以后，head2和head1同时向前走，知道head1知道NULL指针，head2的即为倒数第k个指针。
代码：
#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;}