2.1 寻找链表中倒数第 k 个节点

题目

返回倒数第 k 个节点 - 力扣（LeetCode）

实现一种算法，找出单向链表中倒数第 k 个节点。返回该节点的值。

注意： 本题相对原题稍作改动

示例：

输入：

head = 1->2->3->4->5 和 k = 2  

输出：

4  

说明： 给定的 k 保证是有效的。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
        
    }
};

分析

考虑到链表遍历的时候，只能单向遍历，因此想要寻找到倒数第K个节点，需要把节点的相对距离信息蕴含在单次遍历中。

设定节点为node，节点大小为node->size()，那么倒数第K个节点的位置有两个，那么相对于头的距离是node->size() - K，相对于末尾的距离是K - 1。
也就是说，这道题有两种处理方法：

1. 先获取节点的长度 node->size()，然后node->size() - K就是倒数第K个节点的位置。
2. 产生一对间隔为K - 1的节点，两个节点同时步进，后面那个节点到达末尾的时候，前面那个节点就从倒数第K个节点。

从1开始计数，比如有 1 2 3 4 5 ，K = 2 的时候数据如下：

1       2       3       4       5
|<--------- 3 --------->|
                        |<- 1 ->|
                        * Node
# 相对于头部节点的距离：3 = 5 - 2
# 相对末尾节点的距离：1 = 2 - 1

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    int kthToLast(ListNode* head, int k) {
	    if (!head) {
            return -1;
	    }
	    ListNode *kthOfNode = head;
        for (size_t i = 1; i < k; ++i) {
            if (head->next) {
                head = head->next;
            } else {
                return -1;
            }
        }
        while (head->next) {
            head = head->next;
            kthOfNode = kthOfNode->next;
        }
        return kthOfNode->val;
    }
};

*****