Thursday, April 8, 2010

Middle of a linked list

Method1 (Uses one slow pointer and one fast pointer)
// 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;

       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.

Method2(Uses a counter)

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++)
     else if ((i%2)==1)
   return middle;

No comments:

Post a Comment