</>EmbeddedInterview

How do you find the middle of a linked list in one pass?

EasyData Structures & Algorithms

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).