剑指 Offer 22. 链表中倒数第k个节点

思路

方法：快慢指针

初始时，p，q都指向链表头节点，让q比p先走k步，之后p，q一起走，每次一步，当q为NULL的时候，p指向的就是倒数第k个节点。

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode* getKthFromEnd(ListNode* head, int k) {
12         ListNode* p, *q;
13         p = q = head;
14         //初始时，q在p前面k步的位置
15         for(int i = 0; i < k; ++i) {
16             q = q->next;
17         }
18 
19         while(q) {
20             p = p->next;
21             q = q->next;
22         }
23 
24         return p;
25     }
26 };

复杂度分析：

时间复杂度：O(n)

空间复杂度：O(1)