# 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;

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;
}
}
va_end(argp);
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  == 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.