专栏首页code秘密花园《剑指offer》11.链表中倒数第k个节点

《剑指offer》11.链表中倒数第k个节点

题目

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

思路

简单思路: 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。

优化:设定两个节点,间距相差k个节点,当前面的节点到达终点,取后面的节点。

前面的节点到达k后,后面的节点才出发。

本题目着重考察代码鲁棒性、容错率: 需要考虑head为null,k为0,k大于链表长度的情况

代码

function FindKthToTail(head, k) {
      if (!head || !k) return null;
      let front = head;
      let behind = head;
      let index = 1;
      while (front.next) {
        index++;
        front = front.next;
        if (index > k) {
          behind = behind.next;
        }
      }
      return (k <= index) && behind;
    }

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构,操作复杂。由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一种线性表顺序表快得多,但是查找一个节点或者访问特定编号的节点则需要O(n)的时间,而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

本文分享自微信公众号 - code秘密花园(code_mmhy),作者:ConardLi

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-01-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 《剑指offer》第11期:两个链表题目

    简单思路: 循环到链表末尾找到 length 在找到length-k节点 需要循环两次。

    ConardLi
  • 【算法专栏】二叉树的下一个节点

    给定一个二叉树和其中的一个结点,请找出中序遍历顺序的下一个结点并且返回。注意,树中的结点不仅包含左右子结点,同时包含指向父结点的指针。

    ConardLi
  • 《剑指offer》最小的k个数

    输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。

    ConardLi
  • JS手动实现一个链表

    链表是一个「线性」结构,充分利用了计算机的内存空间,实现了灵活的内存状态管理。在物理存储结构上,链表是不连续、无顺序的存储结构,在逻辑上,通过使用节点的引用实现...

    不作声
  • 在phpstudy集成环境下的nginx服务器下配置url重写

    直接在对应的vhosts.conf配置文件的location / {}中添加以下内容:

    砸漏
  • Apache2为什么会自动加载index.php

    我直接输入域名后,Apache2自动加载了对应目录下的index.php, 这是怎么做到的?

    Jerry Wang
  • ArrayList与LinkedList 源码分析(基于JDK1.7)

    List接口中的方法有很多,但最重要的无非是增删查改,我们从ArrayList与LinkedList的实现上来讨论他们的增删查改性能问题。先列出这几个重要的方法...

    日薪月亿
  • 封装Python列表实现多下标访问

    class MyArray(object): def __init__(self, values): #values can be of...

    Python小屋屋主
  • 数据结构与算法系列2 线性表 使用java实现动态数组+ArrayList源码详解

    对数组有不了解的可以先看看我的另一篇文章,那篇文章对数组有很多详细的解析,而本篇文章则着重讲动态数组,另一篇文章链接如下,可点击跳转: 链接:https://...

    一只胡说八道的猴子
  • 452. 删除链表中的元素基本操作。链表

    删除链表中等于给定值val的所有节点。 样例 给出链表 1->2->3->3->4->5->3, 和 val = 3, 你需要返回删除3之后的链表:1->2...

    和蔼的zhxing

扫码关注云+社区

领取腾讯云代金券