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

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
#include

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
#include

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