How do you find the middle of a linked list in one pass?
Short answer: Use slow and fast pointers: advance slow by one and fast by two; when fast reaches the end, slow is at the middle. For an even number of nodes this returns the second of the two middle nodes; to get the first one, loop while fast->next && fast->next->next.
struct node *middle(struct node *h) /* second middle for even lengths */
{
struct node *slow = h, *fast = h;
while (fast && fast->next) { slow = slow->next; fast = fast->next->next; }
return slow;
}
struct node *middle_first(struct node *h) /* first middle for even lengths */
{
if (!h) return NULL;
struct node *slow = h, *fast = h;
while (fast->next && fast->next->next) { slow = slow->next; fast = fast->next->next; }
return slow;
}
Uses: splitting a list for merge sort (use the first-middle version so both halves are non-empty), palindrome checks, and finding the k-th node from the end (move one pointer k steps ahead, then advance both until the leader reaches the end).