Find Middle Element of Linked List in DSA C

Mental Model

To find the middle element, use two pointers moving at different speeds so when the fast one reaches the end, the slow one is in the middle.

Analogy: Imagine two friends walking on a path: one walks twice as fast as the other. When the faster friend reaches the end, the slower friend is exactly halfway.

head -> 1 -> 2 -> 3 -> 4 -> 5 -> null
slow ↑
fast ↑

Dry Run Walkthrough

Input: list: 1 -> 2 -> 3 -> 4 -> 5 -> null

Goal: Find the middle element of the linked list

Step 1: Initialize slow and fast pointers at head (node 1)

head -> [slow->1, fast->1] -> 2 -> 3 -> 4 -> 5 -> null

Why: Both pointers start at the beginning to start traversal

Step 2: Move slow pointer one step to node 2, fast pointer two steps to node 3

head -> 1 -> [slow->2] -> [fast->3] -> 4 -> 5 -> null

Why: Slow moves one step, fast moves two steps to find middle efficiently

Step 3: Move slow pointer one step to node 3, fast pointer two steps to node 5

head -> 1 -> 2 -> [slow->3] -> 4 -> [fast->5] -> null

Why: Continue moving pointers until fast reaches end

Step 4: Try to move fast pointer two steps but reaches null, stop

head -> 1 -> 2 -> [slow->3] -> 4 -> 5 -> null

Why: Fast pointer reached end, slow pointer is at middle

Result:

head -> 1 -> 2 -> [3] -> 4 -> 5 -> null
Middle element is 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdlib.h>

// Node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Function to find middle element
int findMiddle(Node* head) {
    if (head == NULL) return -1; // empty list

    Node* slow = head;
    Node* fast = head;

    while (fast != NULL && fast->next != NULL) {
        slow = slow->next; // move slow one step
        fast = fast->next->next; // move fast two steps
    }

    return slow->data; // slow is at middle
}

// Function to print linked list
void printList(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        printf("%d -> ", curr->data);
        curr = curr->next;
    }
    printf("null\n");
}

int main() {
    // Create linked list 1->2->3->4->5->null
    Node* head = createNode(1);
    head->next = createNode(2);
    head->next->next = createNode(3);
    head->next->next->next = createNode(4);
    head->next->next->next->next = createNode(5);

    printList(head);
    int middle = findMiddle(head);
    printf("Middle element is %d\n", middle);

    return 0;
}

while (fast != NULL && fast->next != NULL) {

continue loop while fast pointer and next node exist

slow = slow->next; // move slow one step

advance slow pointer by one node to approach middle

fast = fast->next->next; // move fast two steps

advance fast pointer by two nodes to reach end faster

return slow->data; // slow is at middle

slow pointer now points to middle node, return its data

Output

1 -> 2 -> 3 -> 4 -> 5 -> null

Middle element is 3

Complexity Analysis

Time: O(n) because we traverse the list once with two pointers

Space: O(1) because only two pointers are used regardless of list size

vs Alternative: Better than counting nodes first then traversing again, which takes two passes (O(2n))

Edge Cases

Empty list

Returns -1 indicating no middle element

DSA C

if (head == NULL) return -1; // empty list

List with one element

Returns the single element as middle

DSA C

while (fast != NULL && fast->next != NULL)

List with even number of elements

Returns the second middle element (e.g., for 4 elements returns 3rd node)

DSA C

while (fast != NULL && fast->next != NULL)

When to Use This Pattern

When you need to find the middle of a linked list efficiently, use two pointers moving at different speeds to find it in one pass.

Common Mistakes

Mistake: Moving both pointers one step at a time and then counting steps to find middle
Fix: Move one pointer twice as fast as the other to find middle in one traversal

Mistake: Not checking if fast or fast->next is NULL before moving fast two steps
Fix: Add condition while (fast != NULL && fast->next != NULL) to avoid null pointer errors

Summary

Finds the middle element of a linked list using two pointers moving at different speeds.

Use when you want to find the middle node in a single pass without counting nodes first.

The slow pointer will be at the middle when the fast pointer reaches the end.