剑指offer14：输入一个链表，输出该链表中倒数第k个结点。

1. 题目描述

　　输入一个链表，输出该链表中倒数第k个结点。

2. 思路和方法

　　可以用两个指针，一个指针遍历到第k个结点的时候，第二个指针再走到第一个节点，然后两个指针的距离始终保持k-1。这样，当第一个指针的next==NULL，也就是走到最后一个节点的时候，第二个指针对应的位置，就是倒数第k个结点。这样的好处是能够节省一个循环，时间复杂度会相应降低，从Q(2N) 降低到到Q(N)。

　　注意，但是需要一个小循环让第一个指针先走到第k个指针。同时也存在结点总数小于k的问题，如果循环还没有进行到k次，而第一个指针的已经是NULL，即走到头了，那么，函数返回NULL。

3. C++核心代码

 /*
 struct ListNode {
     int val;
     struct ListNode *next;
     ListNode(int x) :
             val(x), next(NULL) {
     }
 };*/
 class Solution {
 public:
     ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
         ListNode* p = pListHead;
         ListNode* q = pListHead;
         int i = ;
         for(;p != NULL;i++)
         {
             if(i >= k)
             {
                 q = q->next;
             }
             p = p->next;
         }
         return i < k ? NULL:q;
     }
 };

4. C++完整代码

 #include <vector>
 #include <algorithm>
 #include <string.h>
 #include <iostream>
 #include <stack>

 using namespace std;

 struct ListNode{
     int val;
     struct ListNode *next;
     ListNode(int x) :
         val(x), next(NULL){}
 };

 class Solution{
 public:
     ListNode * FindKthToTail(ListNode* pListHead, unsigned int k){
         ListNode* first = pListHead;
         ListNode* second = pListHead;
         int i = ;
         if (first == NULL)
             return NULL;
         for (i; i <= k; i++){
             if (first->next == NULL)
                 break;
             first = first->next;
         }
         while (first->next != NULL){
             first = first->next;
             second = second->next;
         }
         return second;
     }
 };
 int main() {

     struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
     struct ListNode* r = (struct ListNode*)malloc(sizeof(struct ListNode));

     p->val = ;
     p->next = NULL;

     for (int i = ; i>; i--){
         struct ListNode* t = (struct ListNode*)malloc(sizeof(struct ListNode));
         t->val = i;
         t->next = p->next;
         cout << "t->next地址="<< t->next << endl;
         p->next = t;
         cout << "   p->next地址=" << p->next << endl;
     }
     cout << "p->val" << endl;
     for (int i = ; i < ; i++){
         if (p->next != NULL){
             cout << p->val << " ";
             p = p->next;
         }
     }
     cout << endl;

     Solution s;
     r = s.FindKthToTail(p, );
     cout << "r->val = " << r->val << endl;

     system("pause");
     return ;
 }

参考代码

https://blog.****.net/yummy_alice/article/details/81358894

https://blog.****.net/u013686654/article/details/73827816