剑指Offer——链表中倒数第k个结点

题目描述：

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

分析：

定义两个指针p、q，只需让p先走k步，然后q再走，那么p到终点了，q指向的结点就是倒数第k个结点。

代码：

 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         struct ListNode *p, *q;
13         p = q = pListHead;
14         unsigned int i = 0;
15         while(p) {
16             if(i >= k)  // q指针比p指针慢走k步
17                 q = q->next;
18             p = p->next;
19             i++;
20         }
21         return i < k ? NULL : q;
22     }
23 };