常量space，过一遍，日常打码题

Question

这是每日编码问题：

“给定一个单链表和一个整数k，从列表中删除倒数第k个元素。 k保证小于列表的长度。

名单很长，所以不止一次通过是非常昂贵的。

持续 space 一次完成。”

...

这是我的解决方案：

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项使得space在kth和end=k之间，然后递增kth和previous，等待end.next == null，此时，kth 将指向从最后一个元素开始的第 k 个，而 previous 指向它之前的那个。然后通过 previous.next = kth.next.

将列表拼接回去

我的问题是：

这是常数Space吗？是一关吗？

谢谢。

Answer 1

是的，只有一个循环遍历列表，因此您只进行一次。无论输入的大小如何，您都分配相同的三个变量，因此您也使用常量 space.

Answer 2

Python解决方案

class Node:
    def __init__(self, val, next=None):
        self.val = val
        self.next = next


def kthLast(node, k):
    count = 0
    p0 = node
    current = node

    while current:
        count += 1
        if count > k:
            p0 = p0.next

        current = current.next

    return p0.val

Answer 3

使用std::forward_list:

using namespace std;

#include <forward_list>

void removeKthElementFromEnd(forward_list<int>& l, int k)
{
    forward_list<int>::iterator it, it_k;
    it_k = l.begin();
    for(it = l.begin(); it != l.end(); it++)
    {
        if (k < 0)
            it_k++;
        k--;
    }
    l.erase_after(it_k);
}

int main()
{
    forward_list<int> l;
    l.assign({ 1,2,3,4,5,6,7,8,9 });
    int k = 3;

    removeKthElementFromEnd(l, k);

    return 0;
}

常量space，过一遍，日常打码题

Constant space, one pass, daily coding problem

javascript

complexity-theory

time-complexity

space-complexity