这是每日编码问题:
“给出一个单链表和一个整数k,从列表中删除第k个最后一个元素。 k保证小于列表的长度。
名单很长,因此多于一张通行证的费用过高。
在恒定的空间内一次完成此操作。”
...
这是我的解决方案:
function removeKthFromEnd() {
var previous = list.head;
var kth = list.head;
var end = list.head;
for(var i = 0; i < k; i++){
end = end.next;
}
while(end != null) {
previous = kth;
end = end.next;
kth = kth.next;
}
previous.next = kth.next;
kth = null;
}
我将kth,previous和end设置为列表的开头,遍历链表中的k个项,以使kth与end = k之间的空间,然后递增kth和previous,等待end.next == null,此时,第k个元素将指向最后一个元素的第k个元素,而上一个元素将指向它前面的第一个元素。然后只需通过将previous.next = kth.next缝合起来即可。
我的问题是:
这是在恒定空间吗?是一通吗?
谢谢。
最佳答案
是的,只有一个循环遍历该列表,因此您只进行了一次遍历。无论输入大小如何,您都将分配相同的三个变量,因此您还将使用恒定的空间。