Learn more about Russian war crimes in Ukraine.

How to find the middle of a linked list

Just like my post on How to find the kth last node of a linked list, there are some boring ways to find the middle of a linked list, but at least one exciting way, and it again uses a trick called the “runner”. We set up two pointers into the linked list, fast and slow. They will both iterate over the list, but for each jump made by the slow pointer, the fast pointer will make two jumps. Then, when fast reaches the end of the list, slow will be half-way through!

Note that a list only has a “middle” element if there are an odd number of nodes! When we try to skip the fast pointer by 2, but there’s only one node left, we know that the list has an odd number of nodes, and we can return the slow pointer. Otherwise, we return NULL.

Here’s an implementation in C:

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

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

Node* find_middle(Node* head) {
  Node* fast = head;
  Node* slow = head;
  while (fast != NULL && fast->next != NULL) {
    fast = fast->next->next;
    slow = slow->next;
  if (fast == NULL) {
    // Even number of nodes, so no middle node
    return NULL;
  return slow;

// ----------------------------------------------------
// --------------------- TESTS ------------------------

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

Node* mk_list(int len, ...) {
  Node* list_start = NULL;
  Node* list_end = NULL;
  va_list argp;
  va_start(argp, len);
  for (int i = 0; i < len; i++) {
    Node* node = mk_node(va_arg(argp, int), NULL);
    if (list_start == NULL) {
      list_start = node;
      list_end = node;
    } else {
      list_end->next = node;
      list_end = node;
  return list_start;

int main(int argc, char** argv) {
  assert(find_middle(mk_list(0))== NULL);
  assert(find_middle(mk_list(1, 42))->val == 42);
  assert(find_middle(mk_list(4, 1,2,3,4)) == NULL);
  assert(find_middle(mk_list(5, 1,2,3,4,5))->val == 3);

  return 0;

Here’s a similar implementation in Haskell:

module Runner where

middle :: [a] -> Maybe a
middle xs = g xs xs where
  g (slow:slows) (fast1:fast2:fasts) = g slows fasts
  g slows [_] = Just $ head slows
  g _ _ = Nothing

main = print $
    middle ([] :: [Int]) == Nothing && 
    middle [1] == Just 1 &&
    middle [1,2] == Nothing &&
    middle [1,2,3] == Just 2 &&
    middle [1,2,3,4] == Nothing &&
    middle [1,2,3,4,5] == Just 3

What can computers do? What are the limits of mathematics? And just how busy can a busy beaver be? This year, I’m writing Busy Beavers, a unique interactive book on computability theory. You and I will take a practical and modern approach to answering these questions — or at least learning why some questions are unanswerable!

It’s only $19, and you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

After months of secret toil, I and Andrew Carr released Everyday Data Science, a unique interactive online course! You’ll make the perfect glass of lemonade using Thompson sampling. You’ll lose weight with differential equations. And you might just qualify for the Olympics with a bit of statistics!

It’s $29, but you can get 50% off if you find the discount code ... Not quite. Hackers use the console!

More by Jim

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