边界条件需要注意：两种方法，第一种遍历链表，寻找到节点，然后从头结点开始，寻找第n-k+1个节点；第二种方法，两个指针，第一个先走k-1步，然后第二个指针和第一个一起走，到尾节点的时候，第二个指针指向的节点就是倒数第k个节点了。

 

在程序中两方法没按顺序写。

切记 每次赋值都是赋头指针给p或者q。

  1 #include<iostream>

  2 

  3  

using 

namespace std;

  4 

  5  typedef 

struct List

  6  {

  7      

int data;

  8      

struct List *next;

  9  }List;

 10  

 11  

void HeadCreatList (List *L)

 12  {

 13      List *s;

 14      L->next=NULL;

 15      

for (

int i=

0;i<

10;i++)

 16      {

 17          s=

new List;

 18          s->data=i;

 19          s->next=L->next;

 20          L->next=s;

 21      }

 22  }

//

头插法建立链表

 23 

 

void TailCreatList(List *L)

 24  {

 25      List *s,*r;

 26      r=L;

 27      

for (

int i=

0;i<

10;i++)

 28      {

 29          s = 

new List;

 30          s->data=i;

 31          r->next=s;

 32          r=s;

 33      }

 34      r->next=NULL;

 35  }

//

尾插法建立链表

 36 

 

void DisPlay(List *L)

 37  {

 38      List *p=L->next;

 39      

while(p!=NULL)

 40      {

 41          cout << p->data;

 42          p = p->next;

 43      }

 44      cout << endl;

 45  }

 46 

void FindBackKthNode_1(List *L,

int k)

 47 {

 48     

if(L == NULL)

 49         

return ;

 50     List *p,*q;

 51     p = L;

 52     q = L;

 53     

int i;

 54     

for(i = 

0;i<k;i++)

 55     {

 56         

if(p->next == NULL)

 57         {

 58             cout << 

"

K is too big

" << endl;

 59             

return ;

 60         }

 61         

else

 62             p = p->next;

 63     }

 64     

while(p!=NULL)

//

p!=NULL保证遍历到最后一个节点

 65 

    {

 66         p = p->next;

 67         q = q->next;

 68     }

 69     cout << q->data <<endl;

 70 }

 71 

void FindBackKthNode_2(List *L ,

int k)

 72 {

 73     

if(L == NULL)

 74         

return ;

 75     List *p = L->next;

 76     

int num = 

0;

 77     

while(p)

 78     {

 79         p = p->next;

 80         num++;

 81     }

 82     

if(num<k)

 83     {

 84         cout << 

"

K is too big

" << endl;

 85         

return ;

 86     }

 87     

else 

if(num == k)

 88     {

 89         p = L->next;

 90         cout << p->data << endl;

 91     }

//

这种方法的边界条件不好，需要加特殊判断

 92 

    

else 

if(num > k)

 93     {

 94         p = L;

//

注意此处要将头结点给p,不然下面的循环条件要改成num-k-1

 95 

        

for(

int i = 

0;i<num-k;i++)

 96         {

 97             p = p->next;

 98         }

 99         cout << p->data << endl;

100     }

101 }

102  

int main()

103  {

104      List *a = 

new List;

105      List *b = 

new List;

106      HeadCreatList(a);

107      TailCreatList(b);

108      DisPlay(a);

109      DisPlay(b);

110      FindBackKthNode_1(a,

5);

111      FindBackKthNode_2(b,

5);

112      system(

"

pause

");

113 

114      

return 

0;

115  }