Middle of a linked list

Problem

Find the middle node of the linked list.
Follow up - How will you get it in first pass.

Solution

Method 1 - Get the length and travel to middle
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 - Uses one slow pointer and one fast pointer
  Traverse linked list using two pointers. Move one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list. This is done in single pass.

// The slow pointer is advanced only by one node
// and the fast pointer is advanced by two nodes!
typedef struct node
{
  int value;
  struct node *next;
  struct node *prev;
}mynode ;



void getTheMiddle(mynode *head)
{
  mynode *p = head;
  mynode *q = head;

  if(q!=NULL)
  {
       while((q->next)!=NULL && (q->next->next)!=NULL)
       {
          p=(p!=(mynode *)NULL?p->next:(mynode *)NULL);
          q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
          q=(q!=(mynode *)NULL?q->next:(mynode *)NULL);
       }
       printf("The middle element is [%d]",p->value);
  }
}

Here p moves one step, where as q moves two steps, when q reaches end, p will be at the middle of the linked list.

Method 3 - Using a counter
Initialize mid element as head and initialize a counter as 0. Traverse the list from head, while traversing increment the counter and change mid to mid->next whenever the counter is odd. So the mid will move only half of the total length of the list.

Pseudocode

Function CAll
   middle = getTheMiddle(head);
Function definition 

// Function to get to the middle of the LL
mynode *getTheMiddle(mynode *head)
{
  mynode *middle = (mynode *)NULL;
  int i;

  for(i=1; head!=(mynode *)NULL; head=head->next,i++)
  {
     if(i==1)
        middle=head;
     else if ((i%2)==1)
        middle=middle->next;
   }
 
   return middle;
}

Thanks. Please write comments if you find anything incorrect.

Follow up - How will you get it in first pass

Method 2 and Method 3 can be used for finding the middle node in single pass. Also, method 2 and 3 are essentially the same.