Constant space, one pass, daily coding problem

Question

This is the Daily Coding Problem:

“Given a singly linked list and an integer k, remove the kth last element from the list. k is guaranteed to be smaller than the length of the list.

The list is very long, so making more than one pass is prohibitively expensive.

Do this in constant space and in one pass.”

...

Here is my solution:

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;
}

I set kth, previous and end to the head of the list, traverse k items through the linked list so that space between kth and end = k, then increment kth and previous, waiting for end.next == null, at which point, kth will point to the kth from last element, and previous points to the one right before it. Then just stitch the list back by making previous.next = kth.next.

My question is:

Is this in Constant Space? Is it one pass?

Thanks.

Answer 1

Yes, there's only one loop traversing the list, so you're only making one pass. You allocate the same three variables no matter the size of the input, so you are also using constant space.

Answer 2

Python solution

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

Using 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;
}