Delete the Middle element of the Linked List in C
Delete the Middle element of the Linked List in C
This article has given a singly linked list and will delete the middle element of the given linked list.
Example: The given linked list is 2 -> 4 -> 6 -> 8 ->10 then the output will be 2 -> 4 -> 8 -> 10.
If the given linked list has an even number of nodes, then there are two middle nodes, and we are required to delete the second middle element of the linked list.
Example: The given linked list is 2 -> 4 -> 6 -> 8 ->10 -> 12 then the output will be
2 -> 4 -> 6 ->10 -> 12
Here, we will see the ways to delete the middle element of the linked list
Method 1:
This method will traverse the entire linked list and then count the total number of nodes present in the linked list. After this, we will traverse the list again till the count/2 and delete the node at count/2.
Source Code to implement method 1 in C language:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *next;
};
struct node *start = NULL;
// For inserting the elements in the linked list
void add(int item)
{
struct node *t, *p;
t = (struct node *)malloc( sizeof( struct node ));
if(start == NULL)
{
start = t;
start -> info = item;
start -> next = NULL;
return;
}
else
{
struct node *p = start;
while(p -> next != NULL)
{
p = p -> next;
}
p -> next = t;
p = p -> next;
p -> info = item;
p -> next = NULL;
}
}
// For finding the middle element of the linked list
void middle( struct node * t )
{
struct node *temp = t;
int count = 0, i;
while(temp != NULL)
{
count++;
temp = temp -> next;
}
for(i= 0; i < count/2-1; i++)
t = t -> next;
t -> next = t -> next -> next;
}
// To display the elements of the linked list
void traverse(struct node * t)
{
if(t == NULL)
{
printf(" Linked list is empty\n");
}
while(t -> next != NULL)
{
printf("%d -> ",t -> info);
t = t -> next;
}
printf("%d",t -> info);
}
// Driver Function
int main()
{
int i;
for (i=2; i<12; i+=2)
{
add(i);
}
middle(start);
traverse(start);
return 0;
}
Output: -
Method 2:
This method takes two pointers called slow pointer and fast pointer and traverses the entire linked list via these two pointers. Next, we move the slow pointer by one and the fast pointer by two and check whether the fast pointer reaches the end of the linked list. When it reaches, then the slow pointer will point to the middle element of the list, and at the same time, we will also track the previous of the middle element so that the middle element can be deleted.
Source Code to implement method 2 in C language:
#include<stdio.h>
#include<stdlib.h>
struct node
{
int info;
struct node *next;
};
struct node *start = NULL;
// For inserting the elements in the linked list
void add(int item)
{
struct node *t, *p;
t = (struct node *)malloc( sizeof( struct node ));
if(start == NULL)
{
start = t;
start -> info = item;
start -> next = NULL;
return;
}
else
{
struct node *p = start;
while(p -> next != NULL)
{
p = p -> next;
}
p -> next = t;
p = p -> next;
p -> info = item;
p -> next = NULL;
}
}
// For finding the middle element of the linked list
void middle( struct node * t )
{
struct node *slow = t;
struct node *fast = t;
struct node *prev = NULL;
if(t != NULL)
{
while(fast != NULL && fast -> next != NULL)
{
prev=slow;
slow = slow -> next;
fast = fast -> next -> next;
}
prev -> next = slow -> next;
}
}
// To display the elements of the linked list
void traverse(struct node * t)
{
if(t == NULL)
{
printf(" Linked list is empty\n ");
}
while(t -> next != NULL)
{
printf("%d -> ", t -> info);
t = t -> next;
}
printf("%d\n", t -> info);
}
// Driver Function
int main()
{
int i;
for (i=2; i<14; i+=2)
{
add(i);
}
middle(start);
traverse(start);
return 0;
}
Output: -
