data-structures · intermediate · ~15 min
Slow/fast two-pointer scan; awareness of the even-length convention.
Given the head of a singly-linked list, return the middle node.
If the list has even length, return the one in the second half (i.e. for [1, 2, 3, 4], return the node containing 3, not 2).
The list node:
typedef struct node { int v; struct node *next; } node_t;
Implement node_t *list_middle(node_t *head). Return NULL if head is NULL.
[1, 2, 3, 4, 5] -> node(3)
[1, 2, 3, 4] -> node(3) // even length: second of the two middles
[1] -> node(1)
[1, 2] -> node(2)
NULL -> NULL
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.
Head of a singly-linked list (may be NULL).
Pointer to the middle node (or NULL).
Single pass. O(1) extra memory.
typedef struct node { int v; struct node *next; } node_t;
node_t *list_middle(node_t *head) { /* TODO */ return NULL; }
Counting the length first and then walking n/2 — two passes, not one. Returning the first middle on even lengths (not the convention here).
NULL head; one-node list; two-node list; even and odd lengths.
O(n).
Solve this exercise in the browser editor — compile and run against the test harness, no setup required.