跳至主要內容

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


22. 链表中倒数第k个节点open in new window

🟢   🔖  链表 双指针  🔗 力扣open in new window

题目

给定一个头节点为 head 的链表用于记录一系列核心肌群训练项目编号,请查找并返回倒数第 cnt 个训练项目编号。

示例 1:

输入:head = [2,4,7,8], cnt = 1

输出:8

提示:

  • 1 <= head.length <= 100
  • 0 <= head[i] <= 100
  • 1 <= cnt <= head.length

注意

本题与 LeetCode 第 19 题 相同。

解题思路

使用快慢指针,从 head 开始遍历链表,快指针先出发,两个指针之间相差 cnt,当快指针到达链尾时,满指针正好指向第 cnt 个节点。

代码

/**
 * @param {ListNode} head
 * @param {number} cnt
 * @return {ListNode}
 */
var trainingPlan = function (head, cnt) {
	let fast = head;
	let slow = head;
	for (let i = 0; i < cnt; i++) {
		fast = fast.next;
	}
	while (fast) {
		fast = fast.next;
		slow = slow.next;
	}
	return slow;
};