# How to find kth last node of a linked list

Question 2.2 of Cracking the Coding Interview:

Implement an algorithm to find the kth to last element of a singly linked list.

There are some boring ways to answer this question, but at least one exciting way.

Boring answer 1: if we know the length l of the list in advance, we can just skip over l - 1 - k nodes.

Boring answer 2: if we don’t know the length of the list in advance, we can count all the nodes first to find its length, then skip over l - 1 - k nodes.

The more exciting answer uses a trick called the “runner”. We set up two pointers into the list, k nodes apart from each other, starting at the start of the list. Then we iterate until the leading pointer hits the end. Then the trailing pointer is k nodes from the end!

Here’s an implementation in C:

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

typedef struct Node {
int val;
struct Node * next;
} Node;

Node* kth_last_element(int k, Node* list) {
Node* trailing = list;
for (int i = 0; i <= k; i++) {
if (leading == NULL) return NULL;
}
trailing = trailing->next;
}
return trailing;
}

Node* mk_node(int val, Node* next) {
Node* node = malloc(sizeof(Node));
node->val = val;
node->next = next;
return node;
}

Node* mk_test_list(int length) {
if (length <= 0) return NULL;
return mk_node(length-1, mk_test_list(length-1));
}

int main(int argc, char** argv) {
// Indexing empty list should always return NULL
assert(kth_last_element(0, NULL) == NULL);
assert(kth_last_element(3, NULL) == NULL);

// List nodes contain their indexes: 9,8,7,6,5,4,3,2,1,0
Node* test_list = mk_test_list(10);

// 0th element from right contains 0, etc
assert(kth_last_element(0, test_list)->val == 0);
assert(kth_last_element(5, test_list)->val == 5);

// Out-of-bounds should return NULL
assert(kth_last_element(15, test_list) == NULL);

return 0;
}
``````

### More by Jim

Tagged #ctci, #programming, #c. All content copyright James Fisher 2020. This post is not associated with my employer. Found an error? Edit this page.