find_middle_1.c

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

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

Node * createNode(int val){
  Node * temp = (Node *)malloc(sizeof(Node));
  if(temp){
    temp->data = val;
    temp->next = NULL;
  }
  return temp;
}
/* This function inserts node at the head of linked list */
void push(Node **headRef, int data){
	Node * newNode  = createNode(data);
	newNode->next = *headRef;
	*headRef  = newNode;
}
void printList(Node *head){
	while(head){
		printf("%d->", head->data);
		head = head->next;
	}
	printf("Null");
}

/* Function to find middle node using traversing twice */
Node * findMiddleNode(Node * head){
	if(!head) return NULL;
	
	Node *current  = head;
	int counter = 0;
	while(current){
		counter++;
		current = current->next;
	}
	// Find half of number of nodes of list
	int middle = counter/2;
	//re-initialise variables.
	counter = 0;
	current = head;
	while(counter < middle){
		counter++;
		current = current->next;
	}
	return current;
}

int main(void) {
	
	Node * head = NULL;
	push(&head, 3);
	push(&head, 4);
	Node * nodeToDelete = head;
	push(&head, 5);
	push(&head, 6);
	push(&head, 7);
	push(&head, 8);
	push(&head, 9);
	printf("\nOriginal list :");
	printList(head);
	Node *mid = findMiddleNode(head);
  printf("\nMiddle node : %d",  mid ? mid->data : 0);
	return 0;
}