Find Middle Element of Linked List in DSA C - Time & Space Complexity

Time Complexity: Find Middle Element of Linked List

O(n)

Understanding Time Complexity

We want to know how the time to find the middle element in a linked list changes as the list grows.

How many steps does it take to reach the middle as the list gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

struct Node {
    int data;
    struct Node* next;
};

int findMiddle(struct Node* head) {
    struct Node* slow = head;
    struct Node* fast = head;
    while (fast != NULL && fast->next != NULL) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow->data;
}
    

This code uses two pointers moving at different speeds to find the middle node of a linked list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The while loop that moves the fast pointer two steps and the slow pointer one step each time.
• How many times: About half the number of nodes in the list, since fast moves twice as fast.

How Execution Grows With Input

As the list size grows, the number of loop steps grows roughly half as fast.

Input Size (n)	Approx. Operations
10	5
100	50
1000	500

Pattern observation: The steps increase linearly with input size, just about half as many steps as nodes.

Final Time Complexity

Time Complexity: O(n)

This means the time to find the middle grows directly with the number of nodes in the list.

Common Mistake

[X] Wrong: "Since the fast pointer jumps two steps, the time complexity is O(n/2), which is faster than O(n)."

[OK] Correct: We ignore constants in Big-O, so O(n/2) is the same as O(n). The time still grows linearly with input size.

Interview Connect

Understanding this method shows you can use clever pointer techniques to solve problems efficiently, a skill valued in many coding challenges.

Self-Check

"What if we used only one pointer to traverse the list once and counted nodes first, then traversed again to the middle? How would the time complexity change?"