找出链表中倒数第 k 个结点

 1 /*
 2 题目:输入一个单向链表,输出该链表中倒数第 k 个结点。链表的倒数第 0 个结点为链表
 3 的尾指针。
 4 链表结点定义如下:
 5 struct node
 6 {
 7     int data;
 8     struct node *next;
 9 };
10 typedef struct node* PtrToNode; 
11 typedef PtrToNode Position;
12 typedef Position List;
13 */
14 #include <iostream>
15 #include <assert.h>
16 #include "./List.h"
17 using namespace std;
18 void print_list(List list)
19 {
20     assert(list != NULL);
21     list = First(list);
22     while(list != NULL)
23     {
24         cout<<list->data<<" ";
25         list = list->next;
26     }
27     cout<<endl;
28 }
29 Position get_last_kth(List list, int k)
30 {
31     assert(list != NULL);
32     Position tmp = First(list);
33     while(tmp != NULL && --k >= 0)
34         tmp = tmp->next;
35     if(NULL == tmp)//the length of list <= k
36         return NULL;
37     Position ret = First(list);
38     while(tmp != NULL)
39     {
40         ret = ret->next;
41         tmp = tmp->next;
42     }
43     return ret;
44 }
45 int main(int argc, char const *argv[])
46 {
47     List list = CreateEmptyList();
48     int k;
49     for(int i = 1; i != 20; ++i)
50         PushBack(i, list);
51     print_list(list);
52     while(cin>>k)
53     {
54         Position tmp = get_last_kth(list, k);
55         cout<<"k:"<<k<<" = ";
56         if(tmp == NULL)
57             cout<<"NULL";
58         else
59             cout<<tmp->data;
60         cout<<endl;
61     }
62     return 0;
63 }