这是几个已知解决方案的已知问题，但我目前的努力是尝试找到最有效的解决方法，同时考虑内存使用情况(而不是时间复杂性)。
问题:给定一个大小未知(但可能相当大)的单链表 N , 删除 Kth列表末尾的成员。 0 <= K < N .
如果K是0 , 删除列表的最后一个节点。如果K = N-1 , 删除列表中的第一个节点。
我最初的方法是递归——这是最简单的编写方式，它的时间复杂度是O(N)。 - 遍历列表两次，到最后再返回。
public int removeKLast(Node<T> node, int k) {
if (node.getNext() == null) {
return k;
} else {
int current = removeKLast(node.getNext(), k);
if (current == 0) {
node.setNext(node.getNext().getNext());
}
return current - 1;
}
}
它有一些需要解决的最终情况(比如从列表中删除第一个节点)，但在其他方面足够简单。
我的问题是，此实现意味着整个链表都存储在内存中，并带有与对象相关的开销。我想知道是否可以找到更有效的解决方案(仍在 O(N) 时间内，最多运行列表两次)，最多使用 K在任何给定时间内存中的原始整数。
最佳答案
开始列表遍历。在 K 步之后启动第二个迭代器，然后并行行走。当第一个迭代器到达末尾时，第二个迭代器站在要删除的节点上。
这种方法不能改变 O(n) 的复杂度并执行大约 2n (2n-k) 步操作，但排除了结束查找和删除之间的“延迟”
关于java - 从链表末尾删除第 K 个节点的内存高效方法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47013010/