链表中倒数第k个结点

题目描述

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

两个指针即可,注意处理k=0的情况

public ListNode FindKthToTail(ListNode head, int k) {
    if (head == null || k < 1) {
        return null;
    }
    ListNode kth = null;
    ListNode tmp = head;
    for (int i = 0; i < k - 1 && tmp != null; i++) {
        tmp = tmp.next;
    }
    if (tmp == null) {
        return null;
    }
    kth = head;

    for (; tmp.next != null; tmp = tmp.next) {
        kth = kth.next;
    }

    return kth;
}

网上题解

链接：https://www.nowcoder.com/questionTerminal/529d3ae5a407492994ad2a246518148a?answerType=1&f=discussion
来源：牛客网

解法 1: 两次循环

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

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

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

代码如下：

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）

代码如下：

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;
}