Find the middle node of a singly linked list

Challenge

Find the middle node of a singly-linked list in one pass.

Task

Given the head of a singly-linked list, implement node_t *list_middle(node_t *head) that returns the middle node. For an even-length list, return the node in the second half (for [1,2,3,4], return the node holding 3). The node type is given:

typedef struct node { int v; struct node *next; } node_t;

Input

head: a pointer to the first node (the type node_t is given, with an int v and a next pointer). May be NULL.

Output

node_t *: a pointer to the middle node, or NULL if the list is empty.

Example

[1, 2, 3, 4, 5]   ->   node(3)
[1, 2, 3, 4]      ->   node(3)   (even length: the second of the two middles)
[1]               ->   node(1)
[1, 2]            ->   node(2)
NULL              ->   NULL

Edge cases

• NULL head returns NULL.
• Single-node and two-node lists.

Rules

• Single pass, O(1) extra memory: use slow/fast pointers (do not count the length first).

Why this matters

The two-pointer 'slow/fast' technique is one of the most useful patterns in linked-list problems. Used for cycle detection, splitting in half, palindrome checking — and here, finding the middle in one pass without computing the length first.

Input format

head: pointer to the first node_t (given: int v; node_t *next;); may be NULL.

Output format

node_t *: pointer to the middle node, or NULL if empty.

Constraints

Single pass. O(1) extra memory.

Starter code

typedef struct node { int v; struct node *next; } node_t;
node_t *list_middle(node_t *head) { /* TODO */ return NULL; }

Common mistakes

Counting the length first and then walking n/2 — two passes, not one. Returning the first middle on even lengths (not the convention here).

Edge cases to handle

NULL head; one-node list; two-node list; even and odd lengths.

Complexity

O(n).

Background lessons

• Linked lists
• The two-pointer technique

Up next

• Detect a cycle in a linked list
• Remove the n-th node from a linked list