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

1. 题目描述

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

2. 思路和方法

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

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

3. C++核心代码

 1 /*
 2 struct ListNode {
 3     int val;
 4     struct ListNode *next;
 5     ListNode(int x) :
 6             val(x), next(NULL) {
 7     }
 8 };*/
 9 class Solution {
10 public:
11     ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
12         ListNode* p = pListHead;
13         ListNode* q = pListHead;
14         int i = 0;
15         for(;p != NULL;i++)
16         {
17             if(i >= k)
18             {
19                 q = q->next;
20             }
21             p = p->next;
22         }
23         return i < k ? NULL:q;
24     }
25 };

View Code

4. C++完整代码

 1 #include <vector>                                
 2 #include <algorithm>                
 3 #include <string.h>                 
 4 #include <iostream>   
 5 #include <stack>
 6 
 7 
 8 using namespace std;
 9 
10 
11 struct ListNode{
12     int val;
13     struct ListNode *next;
14     ListNode(int x) :
15         val(x), next(NULL){}
16 };
17 
18 class Solution{
19 public:
20     ListNode * FindKthToTail(ListNode* pListHead, unsigned int k){
21         ListNode* first = pListHead;
22         ListNode* second = pListHead;
23         int i = 0;
24         if (first == NULL)
25             return NULL;
26         for (i; i <= k; i++){
27             if (first->next == NULL)
28                 break;
29             first = first->next;
30         }
31         while (first->next != NULL){
32             first = first->next;
33             second = second->next;
34         }
35         return second;
36     }
37 };
38 int main() {
39 
40     struct ListNode* p = (struct ListNode*)malloc(sizeof(struct ListNode));
41     struct ListNode* r = (struct ListNode*)malloc(sizeof(struct ListNode));
42 
43     p->val = 0;
44     p->next = NULL;
45 
46     for (int i = 10; i>0; i--){
47         struct ListNode* t = (struct ListNode*)malloc(sizeof(struct ListNode));
48         t->val = i;
49         t->next = p->next;
50         cout << "t->next地址="<< t->next << endl;
51         p->next = t;
52         cout << "   p->next地址=" << p->next << endl;
53     }
54     cout << "p->val" << endl;
55     for (int i = 0; i < 20; i++){
56         if (p->next != NULL){
57             cout << p->val << " ";
58             p = p->next;
59         }
60     }
61     cout << endl;
62 
63     Solution s;
64     r = s.FindKthToTail(p, 0);
65     cout << "r->val = " << r->val << endl;
66 
67     
68     system("pause");
69     return 0;
70 }

View Code

参考代码

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

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