剑指offer-链表中倒数第k个结点(2种解法)

【数值的整次方】【2种解法】【剑指offer】

题目描述

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

🔍 关注公众号“心谭博客” / 👉 前往 xxoo521.com

查看更多前端与算法的系列文章，获得更好阅读体验

解法 1: 两次循环

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

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

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

代码如下：

// 原文地址：https://xxoo521.com/2020-01-11-dao-shu-topk/
// ac地址：https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

function FindKthToTail(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）

代码如下：

// 原文地址：https://xxoo521.com/2020-01-11-dao-shu-topk/
// ac地址：https://www.nowcoder.com/practice/529d3ae5a407492994ad2a246518148a

/*function ListNode(x){
    this.val = x;
    this.next = null;
}*/

function FindKthToTail(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;
}