Return the Kth item from the end of a singly-linked list: https://www.interviewcake.com/question/python/kth-to-last-node-in-singly-linked-list

bench-all.sh

#!/bin/bash

set -e -x

# C
make

# JS
./kth-from-end.js

# PyPy
pypy kth-from-end.py

# Swift
./make-swift.sh
./kth-from-end-swift

# CPython
./kth-from-end.py

clean.sh

#!/bin/bash

set -e

make clean
rm -f kth-from-end-swift

kth-from-end.c

/*
https://www.interviewcake.com/question/python/kth-to-last-node-in-singly-linked-list

return the kth item from the end of a singly-linked list.
*/

#include <stdlib.h>
#include <assert.h>

// MARK: - Linked List implementation

struct _list_t {
    void *data;
    struct _list_t *next;
};
typedef struct _list_t list_t;

list_t* list_create(void *data) {
    list_t* l = malloc(sizeof(list_t));
    l->data = data;
    l->next = NULL;
    return l;
}

// MARK: - Ring Buffer implementation
// Note: turns out the ring-buffer solution is actually slower!

struct _ringbuf_t {
    void **items;
    size_t capacity;
    void **last;
    void **first;
};
typedef struct _ringbuf_t ringbuf_t;

ringbuf_t* ringbuf_create(size_t capacity) {
    ringbuf_t *ring = malloc(sizeof(ringbuf_t));
    ring->capacity = capacity;
    ring->items = malloc(capacity * sizeof(void*));
    ring->first = NULL;
    ring->last = NULL;
    return ring;
}

void ringbuf_push(ringbuf_t *ring, void *item) {
    assert(ring != NULL);

    // Reposition 'first':
    if ((ring->first == NULL) || (ring->first == ring->items)) {
        // If this was a virgin ring buffer, start 'first' at the end of the array.
        // If 'first' has reached the start of the array, wrap around to the end.
        ring->first = ring->items + (ring->capacity - 1);
    } else {
        // Otherwise, advance 'first' by one position (towards the start of the array).
        ring->first -= 1;
    }

    // Store the item:
    *(ring->first) = item;

    // Reposition 'last':
    if (ring->last == NULL) {
        // If this was a virgin ring buffer, point 'last' and 'first' at the same item.
        ring->last = ring->first;
    } else if (ring->last == ring->first) {
        // If 'first' has caught up to 'last'... (i.e., if the ring buffer is full)
        if (ring->last == ring->items) {
            // If 'last' has reached the start of the array, wrap around to the end.
            ring->last = ring->items + (ring->capacity - 1);
        } else {
            // Otherwise, advance 'last' by one position (towards the start of the array).
            ring->last -= 1;
        }
    }
}

void* ringbuf_get(ringbuf_t *ring, size_t index) {
    assert(ring != NULL);
    if (index >= ring->capacity) {
        return NULL;
    }
    size_t first_index = (ring->first - ring->items) / sizeof(void*);
    size_t actual_index = (first_index + index) % ring->capacity;
    return ring->items[actual_index];
}

// MARK: - Kth-from-the-end implementations

void* kth_from_end1(list_t *list, size_t k, ringbuf_t *ring) {
    if (list == NULL) {
        return NULL;
    }

    ringbuf_push(ring, list->data);
    size_t i = 1;

    // Push the entire array into the ring buffer:
    while (list->next != NULL) {
        list = list->next;
        ringbuf_push(ring, list->data);
        i++;
    }

    // 'last' is now the kth item from the end of the list (assuming at least k
    // pushes took place)
    if (i <= k) {
        return NULL;
    } else {
        return ring->last;
    }
}

void* kth_from_end2(list_t *list, size_t k) {
    if (list == NULL) {
        return NULL;
    }

    // run through the list once to find the length
    size_t length = 1;
    list_t *lp = list;
    while(lp->next != NULL) {
        lp = lp->next;
        length++;
    }

    if (k >= length) {
        return NULL;
    }

    // run through the list again stopping at length - k
    list_t *kth = list;
    for (size_t i = 1; i < (length - k); i++) {
        kth = kth->next;
    }
    return kth;
}

// MARK: - Unit tests

#include <string.h>
#include <stdio.h>
#include <sys/time.h> // for gettimeofdat()

void test_perf() {
    printf("constructing linked list...\n");
    int k = 0;
    list_t *list = list_create("a");
    list_t *listi = list;
    for (size_t i = 1; i < 100000000L; i++) {
        listi->next = list_create("a");
        listi = listi->next;
    }
    ringbuf_t *ring = ringbuf_create(k+1);

    printf("benchmarking...\n");

    struct timeval then;
    struct timeval now;
    double elapsed1;
    double elapsed2;
    double factor;

    gettimeofday(&then, NULL);
    kth_from_end1(list, k, ring);
    gettimeofday(&now, NULL);
    // thanks to https://stackoverflow.com/a/2150334/7543271
    elapsed1 = (now.tv_sec - then.tv_sec) + (now.tv_usec - then.tv_usec) / 1000000.0;
    printf("kth_from_end1 (ring buffer)    elapsed time: %f seconds (n = 1e8)\n", elapsed1);

    gettimeofday(&then, NULL);
    kth_from_end2(list, k);
    gettimeofday(&now, NULL);
    // thanks to https://stackoverflow.com/a/2150334/7543271
    elapsed2 = (now.tv_sec - then.tv_sec) + (now.tv_usec - then.tv_usec) / 1000000.0;
    printf("kth_from_end2 (traverse twice) elapsed time: %f seconds (n = 1e8)\n", elapsed2);

    factor = 100.0 / ((double)elapsed2 / (double)elapsed1);
    printf("speedup: %0.1f%% faster\n", factor);
}

int main(int argc, char **argv) {
    test_perf();
    return EXIT_SUCCESS;
}

kth-from-end.js

#!/usr/bin/env node

/*
https://www.interviewcake.com/question/python/kth-to-last-node-in-singly-linked-list

return the kth item from the end of a singly-linked list.
*/

function kth_from_end2(list, k) {
    // run through the list once to find the length
    var length = 1;
    var listi = list;
    while (listi.next != null) {
        listi = listi.next;
        length += 1;
    }

    if (k >= length) {
        return null;
    }

    // run through the list again stopping at length - k
    listi = list;
    for (var i = 1; i < (length - k); i++) {
        listi = listi.next;
    }
    return listi.data;
}

function test() {
    var assert = require('assert');

    var list = null;

    var node = {};
    node.data = "a";
    node.next = null;
    list = node;
    assert(kth_from_end2(list, 0) == "a");
    assert(kth_from_end2(list, 1) == null);

    var node = {};
    node.data = "b";
    node.next = null;
    list.next = node;
    assert(kth_from_end2(list, 0) == "b");
    assert(kth_from_end2(list, 1) == "a");

    var node = {};
    node.data = "c";
    node.next = null;
    list.next.next = node;
    assert(kth_from_end2(list, 0) == "c");
    assert(kth_from_end2(list, 1) == "b");
    assert(kth_from_end2(list, 2) == "a");

    var node = {};
    node.data = "d";
    node.next = null;
    list.next.next.next = node;
    assert(kth_from_end2(list, 0) == "d");
    assert(kth_from_end2(list, 1) == "c");
    assert(kth_from_end2(list, 2) == "b");
    assert(kth_from_end2(list, 3) == "a");
}

function test_perf() {
    console.time("creating list (n = 1e7)");
    var list = {};
    list.data = "a";
    list.next = null;
    var listi = list;
    for (var i = 0; i < 10000000; i++) {
        var node = {};
        node.data = "a";
        node.next = null;
        listi.next = node;
        listi = listi.next;
    }
    console.timeEnd("creating list (n = 1e7)");

    var k = 0;

    console.time("traverse twice");
    kth_from_end2(list, k);
    console.timeEnd("traverse twice");
}

test();
test_perf();

kth-from-end.py

#!/usr/bin/env python

# https://www.interviewcake.com/question/python/kth-to-last-node-in-singly-linked-list
# 
# return the kth item from the end of a singly-linked list.


class LinkedList:
    data = None
    next = None

    def __init__(self, data):
        self.data = data

    def append(self, data):
        if self.next is not None:
            self.next.append(data)
        else:
            self.next = LinkedList(data)


# Note: turns out the ring-buffer solution is actually slower!
class RingBuffer:
    def __init__(self, capacity):
        self.items = [None] * capacity
        self.first_index = None
        self.last_index = None
    
    def push(self, item):
        # Reposition 'first':
        if self.first_index is None or self.first_index == 0:
            # If this was a virgin ring buffer, start 'first' at the end of the array.
            # If 'first' has reached the start of the array, wrap around to the end.
            self.first_index = len(self.items) - 1
        else:
            # Otherwise, advance 'first' by one position (towards the start of the array).
            self.first_index -= 1
        
        # Store the item:
        self.items[self.first_index] = item

        # Reposition 'last':
        if self.last_index is None:
            # If this was a virgin ring buffer, point 'last' and 'first' at the same item.
            self.last_index = self.first_index
        elif self.last_index == self.first_index:
            # If 'first' has caught up to 'last'... (i.e., if the ring buffer is full)
            if self.last_index == 0:
                # If 'last' has reached the start of the array, wrap around to the end.
                self.last_index = len(self.items) - 1
            else:
                # Otherwise, advance 'last' by one position (towards the start of the array).
                self.last_index -= 1

    def get(self, index):
        if index > len(self.items):
            return None
        actual_index = (self.first_index + index) % len(self.items)
        return self.items[actual_index]
    
    def last(self):
        return self.get(len(self.items) - 1)


def kth_from_end1(llist, k):
    ring = RingBuffer(k+1)
    ring.push(llist.data)
    i = 1

    # Push the entire array into the ring buffer:
    while llist.next is not None:
        llist = llist.next
        ring.push(llist.data)
        i += 1

    # 'last' is now the kth item from the end of the list (assuming at least k
    # pushes took place)
    if i <= k:
        return None
    else:
        return ring.last()

def kth_from_end2(llist, k):
    # run through the list once to find the length
    length = 1
    listi = llist
    while listi.next is not None:
        listi = listi.next
        length += 1

    if k >= length:
        return None

    # run through the list again stopping at length - k
    listi = llist
    for _ in range(length - k - 1):
        listi = listi.next
    return listi.data


def test():
    llist = LinkedList("a")
    assert kth_from_end1(llist, 0) == "a"
    assert kth_from_end1(llist, 1) == None

    llist.append("b")
    assert kth_from_end1(llist, 0) == "b"
    assert kth_from_end1(llist, 1) == "a"

    llist.append("c")
    assert kth_from_end1(llist, 0) == "c"
    assert kth_from_end1(llist, 1) == "b"
    assert kth_from_end1(llist, 2) == "a"

    llist.append("d")
    assert kth_from_end1(llist, 0) == "d"
    assert kth_from_end1(llist, 1) == "c"
    assert kth_from_end1(llist, 2) == "b"
    assert kth_from_end1(llist, 3) == "a"


def test2():
    llist = LinkedList("a")
    assert kth_from_end2(llist, 0) == "a"
    assert kth_from_end2(llist, 1) == None

    llist.append("b")
    assert kth_from_end2(llist, 0) == "b"
    assert kth_from_end2(llist, 1) == "a"

    llist.append("c")
    assert kth_from_end2(llist, 0) == "c"
    assert kth_from_end2(llist, 1) == "b"
    assert kth_from_end2(llist, 2) == "a"

    llist.append("d")
    assert kth_from_end2(llist, 0) == "d"
    assert kth_from_end2(llist, 1) == "c"
    assert kth_from_end2(llist, 2) == "b"
    assert kth_from_end2(llist, 3) == "a"

def test_perf():
    print "constructing linked list..."
    k = 0
    llist = LinkedList("a")
    listi = llist
    for _ in range(10 * 1000 * 1000):
        listii = LinkedList("a")
        listi.next = listii
        listi = listi.next

    import time
    print "benchmarking..."

    then = time.time()
    kth_from_end1(llist, 0)
    now = time.time()
    elapsed1 = now - then
    print "kth_from_end1 (ring buffer)    elapsed time: %f seconds (n = 1e7)" % elapsed1

    then = time.time()
    kth_from_end2(llist, 0)
    now = time.time()
    elapsed2 = now - then
    print "kth_from_end2 (traverse twice) elapsed time: %f seconds (n = 1e7)" % elapsed2

    factor = 100.0 / (elapsed2 / elapsed1)
    print "speedup: %0.1f%% faster" % factor


if __name__ == "__main__":
    test()
    test2()
    test_perf()

kth-from-end.swift

// (this solution written by Charlie Nowacek)

import Foundation


// A node for a linked list data structure. Holds a generic value and a reference to the next node in the list.
// next may be nil if the node is the last node in the list.
class LinkedListNode<T> {
    var value: T
    var next: LinkedListNode<T>?

    init(value: T, next: LinkedListNode<T>? = nil) {
        self.value = value
        self.next = next
    }
}


// Returns the kth to last node in a linked list.
// Time: O(n)
// Space: O(n)
func kth_to_last_node_using_array<T>(_ k: Int, head: LinkedListNode<T>) -> LinkedListNode<T> {

    // Create a local variable to track the current node
    var currentNode: LinkedListNode<T>? = head

    // Create an indexable array to store the nodes
    var nodeList: [LinkedListNode<T>] = []

    // Walk the node graph and append the nodes into an indexable Array
    while let someCurrentNode = currentNode {
        nodeList.append(someCurrentNode)
        currentNode = someCurrentNode.next
    }

    // Return the kth from last node or die
    return nodeList[nodeList.count - k]
}


// Returns the kth to last node in a linked list.
// Time: O(n)
// Space: O(1)
func kth_to_last_node<T>(_ k: Int, head: LinkedListNode<T>) -> LinkedListNode<T> {

    // Create a local variable to track the current node
    var currentNode: LinkedListNode<T>? = head

    // Walk the node graph to find the total length of the list
    var listLength = 0
    while let someCurrentNode = currentNode {
        listLength += 1
        currentNode = someCurrentNode.next
    }

    // Re-walk the graph, stopping at the kth to last node
    currentNode = head
    while let someCurrentNode = currentNode, listLength > k {
        listLength -= 1
        currentNode = someCurrentNode.next
    }

    // Return that node or die
    return currentNode!
}

let totalNodes: Int = 100_000_000
let startCreateTime = Date()
let firstNode = LinkedListNode(value: 0)
var currentNode = firstNode
for i in 1..<totalNodes {
    let nextNode = LinkedListNode(value: i)
    currentNode.next = nextNode
    currentNode = nextNode
}
let endCreateTime = Date()
print("Created \(totalNodes) nodes in \(endCreateTime.timeIntervalSince1970 - startCreateTime.timeIntervalSince1970) seconds")

let startCalcTime = Date()
assert(kth_to_last_node(totalNodes, head: firstNode).value == 0, "Assertion failed!")
let endCalcTime = Date()
print("Calc \(totalNodes)th node from the end in \(endCalcTime.timeIntervalSince1970 - startCalcTime.timeIntervalSince1970) seconds")

make-swift.sh

#!/bin/bash

set -e

swiftc -static-stdlib -o kth-from-end-swift kth-from-end.swift

Makefile

test: kth-from-end 
	./kth-from-end

kth-from-end: kth-from-end.c
	gcc -Wall -Werror -o kth-from-end kth-from-end.c

clean:
	rm -f kth-from-end

.PHONY: test kth-from-end

output.txt

$ ./bench-all.sh 
+ make
gcc -Wall -Werror -o kth-from-end kth-from-end.c
./kth-from-end
constructing linked list...
benchmarking...
kth_from_end1 (ring buffer)    elapsed time: 1.039906 seconds (n = 1e8)
kth_from_end2 (traverse twice) elapsed time: 0.693343 seconds (n = 1e8)
speedup: 150.0% faster
+ ./kth-from-end.js
creating list (n = 1e7): 2668.084ms
traverse twice: 132.906ms
+ pypy kth-from-end.py
constructing linked list...
benchmarking...
kth_from_end1 (ring buffer)    elapsed time: 0.426833 seconds (n = 1e7)
kth_from_end2 (traverse twice) elapsed time: 0.131776 seconds (n = 1e7)
speedup: 323.9% faster
+ ./make-swift.sh
+ ./kth-from-end-swift
Created 100000000 nodes in 21.49629807472229 seconds
Calc 100000000th node from the end in 4.631134033203125 seconds
+ ./kth-from-end.py
constructing linked list...
benchmarking...
kth_from_end1 (ring buffer)    elapsed time: 8.694891 seconds (n = 1e7)
kth_from_end2 (traverse twice) elapsed time: 1.798412 seconds (n = 1e7)
speedup: 483.5% faster