find_middle_3.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 hare and tortoise algo */
Node * findMiddleNode_1(Node * head){
	//Wrong list, there is no middle node.
	if(!head) return NULL;
	
	Node *fast = head->next;
	Node *slow = head;
	
	while(fast){
		fast = fast->next;
		//check if fast is not null yet
		if(fast)
			fast = fast->next;
		slow = slow->next;
	}
	return slow;
}

/* Function to find middle node using modified hare and tortoise algo */
Node * findMiddleNode_2(Node * head){
	//Wrong list, there is no middle node.
	if(!head) return NULL;
	
	Node *fast = head;
	Node *mid = head;
	int counter = 0;
	
	while(fast){
		//if you and an odd number, it will return 1, else 0
		if(counter & 1) {
			//If couter is odd, move mid to mid's next
			mid = mid->next;
		}
		counter++;
		fast = fast->next;
	}
	return mid;
}

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_2(head);
    printf("\nMiddle node : %d",  mid ? mid->data : 0);
	return 0;
}