Find middle node of a linked list

How do you find the middle node of singly linked list of unspecified length, by traversing the list only once?

Solution:

• Take two pointers p1 and p2.               
• Let p1 and p2 point to head
• p1=p2 = head;
• Advance p1 by one node at a time and p2  by 2 nodes at a time
                          
• p1 = p1->next;                          
• p2 = p2 ->next->next;
             
• When p2 reaches NULL, p1 will be in the middle node.

Here is the code for the same

NODEPTR find_mid_node(NODEPTR head)
{
     NODEPTR t1 ,t2;
     t1 = t2 = head;
     while(t2!=NULL && t2->next!=NULL)
 {
    t1 = t1->next;     
    t2 = t2->next->next;     
        }
     return t1;//this is the midnode
}

How do you reverse a singly linked list?

I have written a recursive solution for reversing a list in this post . Let us discuss non-recursive solution now. 

• Take two pointers p1 and p2 pointing to first and second nodes        
• p1 = head;
• p2 = p1->next;
• p1->next=NULL;  
• Now reverse their links
• p2->next = p1;
• But now the problem is, we have lost track of the third and subsequent nodes. So before reversing the links store third node in p3
                          
• p1 = head;
• p2 = p1->next;
• p3 = p2->next;
• p2->next = p1;                   
             
• Now continue the process of reversing the links for next set of three nodes
• p1 = p2;
• p2 = p3;
• p3 = p3->next;
• Repeat this process until p3 reaches NULL. At this point of time, p2 will be the last node 
• head = p2;

And here is the code for reversing a singly linked list.

NODEPTR reverse_list_nr(NODEPTR head)
 {
      NODEPTR p1,p2,p3;
      p1 = head;
      p2 = p1->next;
      p3 = p2->next;
      p1->next = NULL;
      while(p3!=NULL)
 {
    p2->next = p1;
           p1 = p2;
           p2 = p3;
           p3 = p3->next;
        }
      p2->next = p1;
      return p2; 
}