LeetCode 「简单」LCR140.训练计划 II
题目描述
给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号，请查找并返回倒数第 cnt 个训练项目编号。
示例
输入：head = [2,4,7,8], cnt = 1
输出：8
解答
双指针法
关键思路
双指针法的核心思想是使用两个指针，fast 和 slow，他们之间的距离始终保持为 cnt。当 fast 指针到达链表末尾时，slow 指针刚好指向倒数第 cnt 个节点。
具体步骤
- 初始化指针
- 初始化两个指针
fast和slow，都指向链表的头节点head
- 移动
fast指针
- 将
fast指针向前移动cnt步。如果在移动过程中fast指针提前到达链表末尾（即fast变为null），说明链表长度小于cnt，直接返回null
- 同时移动两个指针
- 当
fast指针到达链表末尾时，slow指针将指向倒数第cnt个节点 - 在移动过程中，每次将
fast和slow指针同时向前移动一步，直到fast指针到达链表末尾
- 返回结果
- 当
fast指针到达链表末尾时，slow指针所指向的节点即为倒数第cnt个节点
Code
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} cnt
* @return {ListNode}
*/
var trainingPlan = function(head, cnt) {
let slow = head, fast = head;
// 先将 fast 指针向前移动 cnt 步
for (let i = 0; i < cnt; ++i) {
// 如果链表长度小于 cnt，返回 null
if (!fast) return null;
fast = fast.next;
}
// 同时移动 fast 和 slow 指针，直到 fast 到达链表末尾
while (fast) {
fast = fast.next;
slow = slow.next;
}
// 此时 slow 指针指向倒数第 cnt 个节点
return slow;
};