返回倒数第k个节点（面试题 02.02）

题目

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

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

示例

输入： 1->2->3->4->5和 k = 2 输出： 4

说明

给定的 k 保证是有效的。

算法

双指针

快指针比慢指针提前走k-1步，然后两个指针同时前进，当慢指针抵达最后一个节点时，快指针指向的节点就是目标节点

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const kthToLast = (head, k) => {
	let fast = head,
		slow = head;
	for (let i = 0; i < k - 1; i++) {
		slow = slow.next;
	}
	while (slow.next) {
		slow = slow.next;
		fast = fast.next;
	}
	return fast.val;
};

栈

遍历节点，依次推入栈；然后根据k值，从栈中弹出k个元素，最后一个被弹出的就是目标节点

export const kthToLast = (head, k) => {
	const stack = [];
	while (head) {
		stack.push(head.val);
		head = head.next;
	}
	while (--k) {
		stack.pop();
	}
	return stack.pop();
};