剑指offer - 链表中倒数第k个结点 - JavaScript

心谭博客

发布于 2020-04-21 15:25:12

3790

发布于 2020-04-21 15:25:12

文章被收录于专栏：YuanXinYuanXin

题目描述：输入一个链表，输出该链表中倒数第 k 个结点。

题目描述

输入一个链表，输出该链表中倒数第 k 个结点。

解法 1: 两次循环

因为要求链表倒数第 k 个节点，也就是求正数第length - k个节点。整体过程如下：

链表又是个单链表，并且没有保存长度信息。所以需要循环一次计算length。
第二次循环找到第length - k个节点。

时间复杂度是 O(N)，需要 2 次循环。

代码如下：

// ac地址：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
// 原文地址：https://xxoo521.com/2020-01-11-dao-shu-topk/
/**
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let length = 0;
    let node = head;
    while (node) {
        ++length;
        node = node.next;
    }

    if (k > length) {
        return null;
    }

    node = head;
    let offset = length - k;
    for (let i = 0; i < offset; ++i) {
        node = node.next;
    }
    return node;
};

解法 2: 快慢(双)指针

准备两个指针：left（慢）和 right（快）。整体过程如下：

right 先向右移动 k 位，此时 index(right) - index(left) = k
left 和 right 一起向右移动，直到 right 抵达边界
由于index(right) - index(left) = k，所以index(left) = index(right) - k = length - k。也就是 left 指针移动到了倒数第 k 个位置

时间复杂度是 O(N)，但仅需要遍历一次。空间复杂度是 O（1）

代码如下：

// ac地址：https://leetcode-cn.com/problems/lian-biao-zhong-dao-shu-di-kge-jie-dian-lcof/
// 原文地址：https://xxoo521.com/2020-01-11-dao-shu-topk/
/**
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let right = head;
    for (let i = 0; i < k; ++i) {
        if (right === null) {
            // 链表长度小于k
            return null;
        }
        right = right.next;
    }

    let left = head;
    while (right) {
        left = left.next;
        right = right.next;
    }

    return left;
};

剑指offer - 链表中倒数第k个结点 - JavaScript

剑指offer - 链表中倒数第k个结点 - JavaScript

题目描述

解法 1: 两次循环

解法 2: 快慢(双)指针

相关题目

更多资料

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐