【脚趾 offer 22 】 链表中倒数第k个节点

前言

数据结构与算法属于开发人员的内功，不管前端技术怎么变，框架怎么更新，版本怎么迭代，它终究是不变的内容。 始终记得在参加字节青训营的时候，月影老师说过的一句话，不要问前端学不学算法。计算机学科的每一位都有必要了解算法，有写出高质量代码的潜意识。

一、题目描述

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

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

这个链表的倒数第 3 个节点是值为 4 的节点。

示例：

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

二、解题思路

问题描述的比较清晰，但是我们如何去获取倒数第k个元素呢？

这里就使用一种常见的方法：快慢指针；定义两个指针，快指针比慢指针多走k步，所以当快指针指向了链表的末尾的时候，慢指针就指向了倒数第k个节点

三、AC代码

var getKthFromEnd = function(head, k) {
    let first = head
    let second = null
    while(k--){
        first = first.next
    }
    second = head
    while(first){
        first = first.next
        second = second.next
    }
    return second
};

时间复杂度: O(n) n为链表的长度 空间复杂度 O(1)

总结

好了，本篇脚趾offer 链表中倒数第k个节点到这里就结束了，我是邵小白，一个在前端领域摸爬滚打的大三学生，欢迎👍评论。