11 返回倒数第K个节点

返回倒数第 k 个节点

题目描述

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

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

示例：

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

说明：

给定的 k 保证是有效的。

代码

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {number}
 */
var kthToLast = function (head, k) {
  const list = [head.val];
  let current = head;
  while (current.next) {
    current = current.next;
    list.push(current.val);
  }
  list.reverse();
  return list[k - 1];
};

优化解答

解析：

我们可以用快慢指针来做这道题。定义两个指针 fast 和 slow，fast 先走 k 步，然后 slow 和 fast 一起走，当 fast 走到链表末尾时，slow 指向的就是倒数第 k 个节点。

代码：

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {number}
 */
var kthToLast = function (head, k) {
  let slow = head;
  let fast = head;
  let count = 1;
  while (fast.next) {
    if (count >= k) slow = slow.next;
    fast = fast.next;
    count++;
  }
  return slow.val;
};