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;
  Node* leading = list;
  for (int i = 0; i <= k; i++) {
    if (leading == NULL) return NULL;
    leading = leading->next;
  }
  while (leading != NULL) {
    leading = leading->next;
    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;
}

This page copyright James Fisher 2020. Content is not associated with my employer. Found an error? Edit this page.

Jim Fisher

CV

Speaking

Blogroll

RSS

TigYog

Kickabout