我写这个算法来找到单链表的Kth元素,我想要你的反馈,因为我想知道是否有更好的版本。在我看来,这是最优化的方式,我已经涵盖了每个边缘情况(我还假设唯一可能的输入是一个数字,如果我删除了这个假设,我会添加另一个if块),但我非常感谢您的反馈。
PS:我也只添加了这两个主要方法(add和findLast)因为我认为只有两个需要找到一个解决方案,但我不确定我是否应该在面试中添加更多(即删除,删除它) ,addAt,isEmpty等)
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
发布于 2018-10-11 09:48:55
要获取最后n个元素的子列表而不先计算长度(请参阅注释):
在采访中,在实施任何内容之前,首先描述计划通常是个好主意。计算第一作品并且在O符号方面没有区别,但我怀疑这是采访者想要看到的。描述你的计划可以避免花时间在面试官可能不会真正感兴趣的事情上。
https://stackoverflow.com/questions/-100002874
复制相似问题