1. 题目描述

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 2 个节点是值为 4 的节点。

示例：

  1. 给定一个链表: 1->2->3->4->5, 和 k = 2.
  2. 返回链表 4->5.

2. 解题思路

对于这个题目，我们可以使用快慢指针来解决，初始化slow和fast两个指针，开始时两个指针都在链表的头部。

首先让快指针fast先走，向后走k个节点，这样快指针和慢指针之间就相差k个节点。之后，两个指针同时向后移动，知道快指针移动到最后一个节点。这时，由于快慢指针之间相差k个节点，所以此时慢指针所指向的节点就是倒数第k个节点。

复杂度分析：

  • 时间复杂度：O(n)，其中n是链表的长度，我们需要遍历整个链表；

  • 空间复杂度：O(n)，其中n是链表的长度，我们需要储存快慢两个指针指向的链表；

    3. 代码实现

    ```javascript /**

    • Definition for singly-linked list.
    • function ListNode(val) {
    • this.val = val;
    • this.next = null;
    • } / /*
    • @param {ListNode} head
    • @param {number} k

    • @return {ListNode} */ var getKthFromEnd = function(head, k) { let slow = head, fast = head; let cur = 0; while(cur < k){

      1. fast = fast.next
      2. cur++

      }

      while(fast){

      1. fast = fast.next
      2. slow = slow.next

      } return slow

}; ```

4. 提交结果

image.png