How to find mid point of singly linked list in a single pass only ?

Question

List => 1 2 3 4 5 6 7 8 9

N=3 Out Put => 1 2 3 6 5 4 7 8 9
N=4 Out Put => 1 2 6 5 4 3 7 8 9
N=5 Out Put => 1 2 7 6 5 4 3 8 9

Answer 1

Is this considered as single pass, traversing the list once but using two variables.

int getMiddle(struct node *p)
{
  int mid;
  struct node *p1,*p2;
  p1=p2=p;
  while(p2->link != NULL && p2->link->link != NULL)    
  {   
    p1=p1->link;    
    p2=p2->link->link;    
  }    
  return p1->data;    
}

Comments

Yes Salil. As I understand this will be good solution to find middle. And for this code the list should contain minimum one node otherwise it leads to segmentation error as we do not have NULL check for head/first node.

But what is the use of integer "mid" here ..   why you are returning data of middle node.

---

good catch,
1. we need to add a check p==null then return.
2. mid is unused variable, compiler warning.
3. One can return the middle node or data on the middle node depends on the case.