【剑指offer 面试题15】链表中倒数第K个结点

思路：

　　定义两个指针同时指向head，第一个指针先走K-1步，随后二个指针同时移动，当第一个指针到末尾处时，第二个指针所指向的即为倒数第K个结点。

 #include <iostream>

 using namespace std;

 struct ListNode

 {

     int val;

     ListNode *next;

     ListNode(int v = ):val(v), next(NULL){}

 };

 ListNode *findLastKthnumber(ListNode **pListHead, unsigned int k)

 {

     if(*pListHead == NULL || k == )

         return NULL;

     ListNode *pFirst = *pListHead;

     ListNode *pSecond = *pListHead;

     for(int i = ; i < k - ; i++)

     {

         pFirst = pFirst->next;

         if(pFirst == NULL)

             return NULL;

     }

     while(pFirst->next != NULL)

     {

         pFirst = pFirst->next;

         pSecond = pSecond->next;

     }

     return pSecond;

 }

 int main()

 {

     ListNode *first = new ListNode();

     ListNode *head = first;

     ListNode *second = new ListNode();

     first->next = second;

     first = first->next;

     ListNode *third = new ListNode();

     first->next = third;

     first = first->next;

     cout<<"初始链表： ";

     ListNode *print = head;

     while(print != NULL)

     {

         cout<<print->val<<"  ";

         print = print->next;

     }

     cout<<endl<<endl;

     cout<<"倒数第零个结点： ";

     ListNode *res = findLastKthnumber(&head, );

     if(res != NULL)

         cout<<res->val<<endl;

     else

         cerr<<"error!"<<endl;

     cout<<"倒数第一个结点： ";

     res = findLastKthnumber(&head, );

     if(res != NULL)

         cout<<res->val<<endl;

     else

         cerr<<"error!"<<endl;

     cout<<"倒数第二个结点： ";

     res = findLastKthnumber(&head, );

     if(res != NULL)

         cout<<res->val<<endl;

     else

         cerr<<"error!"<<endl;

     cout<<"倒数第三个结点： ";

     res = findLastKthnumber(&head, );

     if(res != NULL)

         cout<<res->val<<endl;

     else

         cerr<<"error!"<<endl;

     cout<<"倒数第四个结点： ";

     res = findLastKthnumber(&head, );

     if(res != NULL)

         cout<<res->val<<endl;

     else

         cerr<<"error!"<<endl;

 }

测试结果：

初始链表：

倒数第零个结点： error!

倒数第一个结点：

倒数第二个结点：

倒数第三个结点：

倒数第四个结点： error!