Constant space, one pass, daily coding problem

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

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.

Advertisement

Answer