Efficiently Finding the Middle of a Linked List in C

In embedded systems programming, resource management and algorithmic efficiency are paramount. When working with dynamic data structures like Linked Lists, a common requirement is to find the middle node—whether for splitting the list in Merge Sort or for specific data processing tasks.

While the naive approach involves two passes (counting then traversing), there is a much more elegant and efficient solution: the Two-Pointer Technique, also known as Floyd’s Cycle-Finding Algorithm variation.

The Algorithm: Tortoise and Hare

The concept is simple: we use two pointers, slow and fast.

1. Slow Pointer: Moves one step at a time.
2. Fast Pointer: Moves two steps at a time.

By the time the fast pointer reaches the end of the list, the slow pointer will be exactly at the middle. This allows us to find the middle in a single pass with O(n) time complexity and O(1) space complexity.

C Implementation

Here is the clean implementation of the findMiddle function:

struct ListNode* findMiddle(struct ListNode *head) {
    if (head == NULL) return NULL;
    
    struct ListNode *slow = head;
    struct ListNode *fast = head;
    
    // Move fast by 2 steps and slow by 1 step
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return slow;  // This is the Middle node
}

How It Works: A Step-by-Step Walkthrough

Let’s visualize the process with a list of 5 nodes: 1 → 2 → 3 → 4 → 5

Handling Even-Length Lists

For an even-length list (e.g., 1 → 2 → 3 → 4):

• The logic above returns the 2nd middle (Node 3).
• Modification: If you need the 1st middle (Node 2), simply change the loop condition to: while (fast->next != NULL && fast->next->next != NULL)

Why This Matters in Embedded Systems

In embedded environments (like STM32 or ESP32 development), you often deal with:

• Limited Memory: This algorithm uses O(1) extra memory (only two pointers).
• CPU Cycles: It finishes in one pass, reducing the execution time compared to a count-and-traverse method.
• Cache Efficiency: Minimizing passes over data structures can help in systems with small caches.

Conclusion

Finding the middle of a linked list is a fundamental building block for more complex algorithms. By using the Two-Pointer approach, you ensure your embedded application remains fast and memory-efficient.