Find Middle Element of Linked List

Use two pointers: slow moves one node per step, fast moves two. When fast can no longer advance (reaches the end or the last node’s next is NULL), slow points at the middle for odd length, and for even length this pattern returns the second of the two middle nodes. Time O(n), extra space O(1)—same idea as Floyd’s cycle detection, without the meet test.

C program (return pointer to middle node)

The list is built with insert_begin as in insert at beginning (30, 20, 10 → values 10 20 30). middle(head) returns the node with 20. main prints the list, prints the middle value, then free_list.

head == NULL: return NULL.
Single node: the loop does not run; slow stays at the only node.

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

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

struct Node *insert_begin(struct Node *head, int data)
{
    struct Node *newNode = malloc(sizeof(struct Node));
    if (newNode == NULL)
        return head;

    newNode->data = data;
    newNode->next = head;
    return newNode;
}

struct Node *middle(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;
}

void print_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        printf("%d ", cur->data);
        cur = cur->next;
    }
    printf("\n");
}

void free_list(struct Node *head)
{
    struct Node *cur = head;
    while (cur != NULL) {
        struct Node *next = cur->next;
        free(cur);
        cur = next;
    }
}

int main(void)
{
    struct Node *head = NULL;

    head = insert_begin(head, 30);
    head = insert_begin(head, 20);
    head = insert_begin(head, 10);

    print_list(head);   /* 10 20 30 */

    struct Node *m = middle(head);
    if (m != NULL)
        printf("middle = %d\n", m->data);

    free_list(head);
    return 0;
}

Program output

10 20 30
middle = 20

Overall program flow

Step	Operation	`head`	Notes
1	`head = NULL`, then three `insert_begin` calls	`0x3000`	List `10 → 20 → 30`
2	`print_list(head)`	Unchanged	Output: `10 20 30`
3	`m = middle(head)`	Unchanged	`m` points to node `20` (`0x2000`)
4	`printf` middle value	—	Output: `middle = 20`
5	`free_list(head)`	Freed	All nodes released

Pointer walk inside `middle` (list `10 20 30`)

Addresses: 10 at 0x3000, 20 at 0x2000, 30 at 0x1000.

Phase	`slow`	`fast`	Next `while` test
start	`0x3000`	`0x3000`	`fast` and `fast->next` non-`NULL`
after 1st advance	`0x2000`	`0x1000`	`fast->next` is `NULL` → exit
return	`return slow` → node `20`

Memory layout (example addresses)

Three nodes (same as insert_begin demo)

Address	Node	`data`	`next`	Points to
`0x3000`	`n1` (head)	10	`0x2000`	`n2`
`0x2000`	`n2` (middle)	20	`0x1000`	`n3`
`0x1000`	`n3`	30	`NULL`	nowhere

Visual representation

head (0x3000)
   │
   ▼
┌──────────────┐    ┌──────────────┐    ┌──────────────┐
│ data: 10     │    │ data: 20     │    │ data: 30     │
│ next: 0x2000 ┼───→│ next: 0x1000 ┼───→│ next: NULL   │
└──────────────┘    └──────────────┘    └──────────────┘
     n1                   n2                   n3
  (inserted last)     (inserted 2nd)      (inserted first)
                              ▲
                              └── middle (slow stops here)

Detailed step-by-step: first iteration of `while` in `middle`

When slow and fast both start at head (0x3000):

Line	Code	Before	After
1	`slow = head; fast = head;`	`head = 0x3000`	`slow`, `fast` at `0x3000`
2	`while (fast != NULL && fast->next != NULL)`	`fast` and `fast->next` non-`NULL`	Enter loop
3	`slow = slow->next;`	`slow` at `0x3000`	`slow = 0x2000`
4	`fast = fast->next->next;`	`fast` at `0x3000`	`fast = 0x1000`
5	`while` test again	`fast` at tail	`fast->next == NULL` → exit
6	`return slow;`	—	Pointer to `0x2000` (`20`)

Complexity summary

Operation	Time	Extra space
`middle`	`O(n)` — fast visits each node at most once	`O(1)`
`insert_begin`	`O(1)` per call	`O(1)` per new node
`print_list`	`O(n)`	`O(1)`
`free_list`	`O(n)`	`O(1)`
Whole program (build + print + middle + free)	`O(n)`	`O(n)` nodes stored in the list

The key takeaway is that you can find the middle in one pass without counting n first: slow / fast keeps the middle under your thumb as fast hits the end.

Even length: this loop returns the second middle node. To get the first middle, run one more pass or adjust the advance rule; for a circular list, use cycle logic first.