原题目
面试题 02.02. 返回倒数第 k 个节点
实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。
**注意：**本题相对原题稍作改动
示例：
输入： 1->2->3->4->5 和 k = 2
输出： 4
说明：
给定的 k 保证是有效的。
第一遍解法
头插法会使链表倒序，先使用头插法创建一个新链表，然后返回第k个节点的值即可。
/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:int kthToLast(ListNode* head, int k) {
ListNode *pre = new ListNode(0);while (head != NULL) {
ListNode *cur = new ListNode(head->val);cur->next = pre->next;pre->next = cur;head = head->next;}while (k--) {
pre = pre->next;}return pre->val;}
};
时间复杂度: O(n)
空间复杂度: O(n)
网上好的解法
双指针，第一个指针指向head，第二个指针指向第k个位置的元素，那么第二个指针到链尾的距离为length - k。所以可以同步右移两个指针，当第二个指针指向最后一个元素时，第一个指针就指向倒数第k个元素。 妙啊！
class Solution {
public:int kthToLast(ListNode* head, int k) {
if(head == NULL) //常规判断return 0;ListNode *pre = head; //前指针ListNode *p = head; //后指针 int i = 0; //i用来确保后指针移动到第K个位置while(i < k){
if(p == NULL) return 0;p = p->next;i++;}while(p != NULL){
//相距K个，同步移动，直到后指针到链表尾部。pre = pre->next;p = p->next;}return pre->val;}
};作者：jameswu
链接：https://leetcode-cn.com/problems/kth-node-from-end-of-list-lcci/solution/shuang-zhi-zhen-tong-bu-yi-dong-shuang-100tong-guo/
来源：力扣（LeetCode）
最后，简化了一下上面的代码：
class Solution {
public:int kthToLast(ListNode* head, int k) {
ListNode *p = head;ListNode *q = p;while(--k) {
q = q->next;}while(q->next != NULL) {
p = p->next;q = q->next;}return p->val;}
};
时间复杂度: O(n)
空间复杂度: O(1)
最后的代码
我认为简化版的同步移动可能是比较好的版本。
class Solution {
public:int kthToLast(ListNode* head, int k) {
ListNode *p = head;ListNode *q = p;while(--k) {
q = q->next;}while(q->next != NULL) {
p = p->next;q = q->next;}return p->val;}
};
时间复杂度: O(n)
空间复杂度: O(1)
小结
- 头插法会使链表逆序。
- 链表问题应常考虑双指针的思路。