Find the middle of a given linked list

Question:

Given a singly linked list, find the middle of the linked list.

 For example:

Input linked list is 1->2->3->4->5
Output should be 3.

If there are even nodes, then there would be two middle nodes, we need to print the second middle element.

 For example, if given linked list is 1->2->3->4->5->6 then the Output should be 4.

Algorithms:

Method 1:
Traverse the whole linked list and count the no. of nodes. Now traverse the list again till count/2 and return the node at count/2.

Method 2:
Traverse linked list using two pointers. Move one pointer by one and other pointers by two. When the fast pointer reaches end slow pointer will reach the middle of the linked list.


C program:

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

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

void printMiddle(struct Node *head)
{
    struct Node *slow_ptr = head;
    struct Node *fast_ptr = head;

    if (head!=NULL)
    {
        while (fast_ptr != NULL && fast_ptr->next != NULL)
        {
            fast_ptr = fast_ptr->next->next;
            slow_ptr = slow_ptr->next;
        }
        printf("The middle element is [%d]\n\n", slow_ptr->data);
    }
}

void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node =
        (struct Node*) malloc(sizeof(struct Node));

    new_node->data  = new_data;

    new_node->next = (*head_ref);

    (*head_ref)    = new_node;
}

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

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

    for (i=5; i>0; i--)
    {
        push(&head, i);
    }
        printList(head);
        printMiddle(head);

    return 0;
}

Output:

1->2->3->4->5->NULL
The middle element is [3]