题目描述

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

思路

使用快慢指针，先让快指针先走k步，然后两个指针一起走，当快指针走到尽头的时候，慢指针所指向的节点就是倒数第k个节点，时间复杂度为$O(n)$,空间复杂度为$O(1)$.

AC代码

#include <iostream>
#include <vector>
#include <stack>
using namespace std;typedef struct ListNode
{int values;struct ListNode *next;
} ListNode, *L;void ListInsert(L &node)
{L p = node;L q = new ListNode; //q为要插入的节点q->next = NULL;     //cin >> q->values;while (p->next != NULL){p = p->next;}q->next = p->next;p->next = q;
}void print(L node)
{while (node != NULL){cout << node->values << endl;node = node->next;}
}class Solution {
public:ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {ListNode * fast = pListHead;ListNode * low = pListHead;while (k > 0 && fast){fast = fast->next;k--; }if (k > 0)   //当K大于0，说明上面的while终止条件是因为fast == NULL,也就是k没有减少0，然后链表就没了，说明k大于链表长度return NULL;while (fast){fast = fast->next;low = low->next;}return low;}
};int main()
{L a;a = new ListNode;a->next = NULL;a->values = 99;for (int i = 0; i < 3; i++){ListInsert(a); //前插法}print(a); //打印链表Solution so;a = so.FindKthToTail(a, 2);cout << a->values <<endl;return 0;
}

总结

• 这种题挺具有参考意义的，面对不支持随机存取的数据结构时，可以采用快慢指针的做法。