首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >Javascript:实现一个算法来找到单个链接字符串的Kth到最后一个元素?

Javascript:实现一个算法来找到单个链接字符串的Kth到最后一个元素?
EN

Stack Overflow用户
提问于 2018-10-11 00:20:43
回答 1查看 0关注 0票数 0

我写这个算法来找到单链表的Kth元素,我想要你的反馈,因为我想知道是否有更好的版本。在我看来,这是最优化的方式,我已经涵盖了每个边缘情况(我还假设唯一可能的输入是一个数字,如果我删除了这个假设,我会添加另一个if块),但我非常感谢您的反馈。

PS:我也只添加了这两个主要方法(add和findLast)因为我认为只有两个需要找到一个解决方案,但我不确定我是否应该在面试中添加更多(即删除,删除它) ,addAt,isEmpty等)

代码语言:javascript
复制
function LinkedList() {
  let length = 0;
  let head = null;

  function Node(element) {
    this.element = element;
    this.next = null;
  }

  this.length = function() {
    return length;
  }

  this.head = function() {
    return head;
  }

  this.add = function(element) {
    let node = new Node(element);

    if (head == null) {
      head = node;
    } else {
      currentNode = head;

      while (currentNode.next) {
        currentNode = currentNode.next;
      }
      currentNode.next = node;
    }
    length++;
  }

  this.findLast = function(index) {
    if(index > length) {
      return false;
    }
    if (index < 0) {
      return false;
    }

    let realIndexes = length-1; // if length = 5, realIndexes = 4
    let realPosition = index-1; // if index = 2, realPosition = 1 
    // We are looking for the real position here.
    let realTarget = realIndexes - realPosition;
    let currentNode = head;
    let counter = 0;

    while (counter < realTarget) {
      currentNode = currentNode.next;
      counter++;
    }
    return currentNode.element;
  }
}

let congo = new LinkedList();
console.log(congo)
congo.add(5);
congo.add("Homeless");
congo.add("Real eyes realize real lies");
congo.length()
congo.head()

输出:=> 5

EN

回答 1

Stack Overflow用户

发布于 2018-10-11 09:48:55

要获取最后n个元素的子列表而不先计算长度(请参阅注释):

  • 继续使用结束指针,直到跳过n个元素。
  • 现在继续与开始指针和结束指针并行,直到结束指针到达列表的末尾(开始结束指针将在你去的时候保持n个元素分开)。
  • 现在开始指向所需的子列表。

在采访中,在实施任何内容之前,首先描述计划通常是个好主意。计算第一作品并且在O符号方面没有区别,但我怀疑这是采访者想要看到的。描述你的计划可以避免花时间在面试官可能不会真正感兴趣的事情上。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/-100002874

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档