从链表末尾删除第 K 个节点的内存高效方法

Question

这是一个有几个已知解决方案的已知问题，但我目前的努力是尝试找到最有效的解决方法，同时考虑内存使用情况（而不是时间复杂性）。

问题：给定一个单链表，大小未知（但可能相当大）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 个原始整数时间。

Answer 1

考虑先检索列表大小：

public int size(Node<T> node) {
   int size = 0;
   if(node != null) {
   for(; node.getNext() != null; node = node.getNext())
       size++;
   }
   return size;
}

然后你可以一次性删除倒数第k个：

public int removeKLast(Node<T> node, int size, int k) {
    for(int i = 0; node = node.getNext() && i < size - k - 1; ++i) {}
    node.setNext(node.getNext().getNext());
}

需要额外的内存：1 个 int 类型的变量（大小）。时间复杂度：O(n).

您没有解释如何存储头节点，因此当您尝试删除第一个节点时，此实现将不起作用。解决此问题所需的修改类似于：

public void removeKLast(Node<T> node, int size, int k) {
    if(k == size - 1) {
        node.setHead(node.getHead().getNext());
    } else {
        for(int i = 0; node = node.getNext() && i < size - k - 1; ++i) {}
        node.setNext(node.getNext().getNext());
    }
}

Answer 2

开始列表遍历。在 K 步之后启动第二个迭代器，然后并行行走。当第一个迭代器到达末尾时，第二个迭代器站在要删除的节点上。

这种方法不能改变O(n)的复杂度并执行大约2n(2n-k)步操作，但不包括"delay"在结束查找和删除之间

从链表末尾删除第 K 个节点的内存高效方法

Memory Efficient Way to Remove Kth Node from End of Linked List

java

algorithm

linked-list

memory-efficient

space-complexity