Tuesday, Aug 21st

Last update12:59:40 PM GMT

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

Write e-mail

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

}
</code>


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)

argaiv1770

#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");

}
</code>


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).

Share this post



Web Hosting