midelement.txt

It is an ebook about data structures,mainly linked list

How do you find the middle of a linked list? Write a C program to return the middle of a linked list 

Discuss it!          

Another popular interview question 

Here are a few C program snippets to give you an idea of the possible solutions. 


Method1 (Uses one slow pointer and one fast pointer) 


#include<stdio.h> 
#include<ctype.h> 

typedef struct node 
{ 
int value; 
struct node *next; 
struct node *prev; 
}mynode ; 



void add_node(struct node **head, int value); 
void print_list(char *listName, struct node *head); 
void getTheMiddle(mynode *head); 

// The main function.. 
int main() 
{ 
mynode *head; 
head = (struct node *)NULL; 

add_node(&head, 1); 
add_node(&head, 10); 
add_node(&head, 5); 
add_node(&head, 70); 
add_node(&head, 9); 
add_node(&head, -99); 
add_node(&head, 0); 
add_node(&head, 555); 
add_node(&head, 55); 

print_list("myList", head); 
getTheMiddle(head); 

getch(); 
return(0); 
} 




// This function uses one slow and one fast 
// pointer to get to the middle of the LL. 
// 
// The slow pointer is advanced only by one node 
// and the fast pointer is advanced by two nodes! 

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); 
} 
} 



// Function to add a node 
void add_node(struct node **head, int value) 
{ 
mynode *temp, *cur; 
temp = (mynode *)malloc(sizeof(mynode)); 
temp->next=NULL; 
temp->prev=NULL; 

if(*head == NULL) 
{ 
*head=temp; 
temp->value=value; 
} 
else 
{ 
for(cur=*head;cur->next!=NULL;cur=cur->next); 
cur->next=temp; 
temp->prev=cur; 
temp->value=value; 
} 
} 



// Function to print the linked list... 
void print_list(char *listName, struct node *head) 
{ 
mynode *temp; 

printf("\n[%s] -> ", listName); 
for(temp=head;temp!=NULL;temp=temp->next) 
{ 
printf("[%d]->",temp->value); 
} 

printf("NULL\n"); 

} 


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) 


#include<stdio.h> 
#include<ctype.h> 

typedef struct node 
{ 
int value; 
struct node *next; 
struct node *prev; 
}mynode ; 



void add_node(struct node **head, int value); 
void print_list(char *listName, struct node *head); 
mynode *getTheMiddle(mynode *head); 

// The main function.. 
int main() 
{ 
mynode *head, *middle; 
head = (struct node *)NULL; 

add_node(&head, 1); 
add_node(&head, 10); 
add_node(&head, 5); 
add_node(&head, 70); 
add_node(&head, 9); 
add_node(&head, -99); 
add_node(&head, 0); 
add_node(&head, 555); 
add_node(&head, 55); 

print_list("myList", head); 
middle = getTheMiddle(head); 
printf("\nMiddle node -> [%d]\n\n", middle->value); 

getch(); 
return(0); 
} 


// 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; 
} 


// Function to add a new node to the LL 
void add_node(struct node **head, int value) 
{ 
mynode *temp, *cur; 
temp = (mynode *)malloc(sizeof(mynode)); 
temp->next=NULL; 
temp->prev=NULL; 

if(*head == NULL) 
{ 
*head=temp; 
temp->value=value; 
} 
else 
{ 
for(cur=*head;cur->next!=NULL;cur=cur->next); 
cur->next=temp; 
temp->prev=cur; 
temp->value=value; 
} 
} 


// Function to print the LL 
void print_list(char *listName, struct node *head) 
{ 
mynode *temp; 

printf("\n[%s] -> ", listName); 
for(temp=head;temp!=NULL;temp=temp->next) 
{ 
printf("[%d]->",temp->value); 
} 

printf("NULL\n"); 

} 




In a similar way, we can find the 1/3 th node of linked list by changing (i%2==1) to (i%3==1) and in the same way we can find nth node of list by changing (i%2==1) to (i%n==1) but make sure ur (n<=i).