剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode）

发布：2021年8月2日22:34:09

问题描述及示例

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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

我的题解

我的题解1（双层`while`循环）

主要思路比较直接，用双层while循环来完成逐个遍历节点并计算当前遍历节点到链尾的距离length。其中，外层while循环用于遍历链表节点，而内层while循环用于计算当前节点到链尾的距离。

用p指针来充当内层循环中的头指针，计算距离length的过程其实也是一种遍历节点的过程。只不过遍历的过程中会同时记录遍历过的节点数量从而达到计算当前节点距离链尾的长度的目的。如果计算得到的长度为k，则说明当前所遍历的节点（也就是head当前的指向）就是我们要找的那个节点。

注意：p指针大概就是充当了一个“侦查兵”的角色。每次head移动到下一个节点时，就让p去探探前面的路有多长。

/**
 * 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) {
  // p指针初始化指向为链首
  let p = head;
  // 外层while循环遍历链表节点
  while (head) {
    // 每次开始计算当前节点到链尾的距离时，都要将length置0
    let length = 0;
    // 内层 while 循环用于计算当前节点到链尾的距离
    while (p) {
      length++;
      p = p.next;
    }
    // 上面计算的长度与k相等，则说明找到了我们想要的节点，返回当前节点
    if (length === k) {
      return head;
    }
    // 如果上面的长度不匹配，则head指向下一个节点，开始重复上面的过程
    head = head.next;
    // 当然也要让侦查小兵p指针回到司令官head的身边以便下一次让p做同样的探路任务
    p = head;
  }
  return null;
};


提交记录
208 / 208 个通过测试用例
状态：通过
执行用时：76 ms, 在所有 JavaScript 提交中击败了85.02%的用户
内存消耗：39.1 MB, 在所有 JavaScript 提交中击败了76.93%的用户
时间：2021/08/02 22:37

上面的解法中用到了双层while循环。这就有种类似穷举的感觉，但不是真正意义上的穷举，因为每次计算完length，都会进行一次判断来决定是否返回，如果k值较大，那么head就不用移动很多次了，反之就会导致多次计算路径。这个复杂度应该和双层for循环是差不多的道理，所以应该也是 O(n²)。