剑指Offer题解 - Day24

「剑指 Offer 22. 链表中倒数第 k 个节点」

力扣题目链接[1]

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

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

「示例：」

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

返回链表 4->5.

思路：

本题涉及到链表，因此优先考虑使用双指针解决。

如果直接采取遍历的话，需要遍历两遍。第一遍用来获取链表的长度，第二遍循环链表长度减去k次，就可以获取到倒数第k个节点。

如果采取双指针的思路，那么这里需要声明两个快慢指针。可以先让快指针走k步，然后两个指针一起走，直到快指针的节点为null ，此时慢指针所处的节点就是倒数第k个节点。

两个指针一起走的时候，可以理解为是一个固定宽度为k的滑动窗口，当窗口的右侧跑到链表末尾时，窗口的左侧就是要寻找的节点。

双指针(快慢指针)

/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */
var getKthFromEnd = function(head, k) {
    let step = k; // 缓存k值，方便让快指针先走k步
    let slow = head; // 初始化慢指针
    let fast = head; // 初始化快指针
    while(step && fast) { // 快指针先走k步
        fast = fast.next;
        step--;
    }
    while(fast) { // 快慢指针一起走，直到快指针的节点为null
        fast = fast.next;
        slow = slow.next;
    }
    return slow; // 返回慢指针
};

• 「时间复杂度 O(n)」。
• 「空间复杂度 O(1)」。

总结

为了防止k越界，这里在第一个while循环中做了不为空的判断处理。第二个while循环使快慢指针一起移动，直到快指针所指节点为null为止。

时间复杂度方面，由于需要遍历整个链表，因此时间复杂度是O(n) ；维护了额外的三个变量，因此空间复杂度是O(1)。

参考资料

[1]力扣题目链接: https://leetcode-cn.com/leetbook/read/illustration-of-algorithm/58tl52/