![\"\"](\"https:\/\/prepbytes-misc-images.s3.ap-south-1.amazonaws.com\/assets\/1645186647086-delete%20middle%20of%20linked%20list.png\")
<\/p>\n<\/p>\n
Linked lists consist of interconnected nodes, with each node containing data and a pointer to the next node in the sequence. Removing the middle node of a linked list poses a significant challenge. Here, we will discuss how to delete middle of linked list in an efficient way. <\/p>\n
The example given below will help in understanding the concept to delete middle element of linked list.<\/p>\n
Input:<\/strong><\/p>\n Since we have to delete middle element of linked list such that the resultant linked list after deletion will be like as shown in the output below.<\/p>\n Output:<\/strong><\/p>\n Explanation:<\/strong> Here we have just made a connection between node(5) and node(15).<\/p>\n Things to observe about the deletion of nodes in a linked list<\/strong><\/p>\n Say, if the deleted node is the target, its previous node is prev and its next node is next1. So, to do the deletion of the target node from the linked list, we need to do the following operations:<\/p>\n Similarly, in this problem, we need to first find the position of the middle node and node previous to the middle node and then following the above-mentioned steps of deletion we have to delete the middle element of the linked list.<\/p>\n So now we will see how to get the middle node and which node will be the middle node of the linked list in case of even length and odd length linked list.<\/p>\n Observations for the position of the middle element of linked list<\/strong><\/p>\n Even Length Linked List:<\/strong><\/p>\n Odd Length Linked List:<\/strong><\/p>\n If there are an odd number of nodes in the linked list, there will be a single middle node, and we will delete that node from the linked list. Note:<\/strong> If there is just one node present in the input linked list, that node should be removed and a new head should be returned.<\/p>\n The naive approach to deleting the middle node is to count the number of nodes N in a linked list first, then delete the (N\/2)th node using the simple deletion method.<\/p>\n The (N\/2)th node is the middle node of the linked list.<\/p>\n Algorithm of Naive Approach to Delete the Middle Node of a Linked List<\/strong> If the head is NULL, return NULL.<\/p>\n<\/li>\n If the next of head is NULL, delete the head and return NULL.<\/p>\n<\/li>\n Create a node Head_copy and make it point to the head.<\/p>\n<\/li>\n Initialize a counter variable count = 0, and now with help of head, traverse the linked list incrementing the count variable by 1 for each node of the linked list.<\/p>\n<\/li>\n Finally, when the traversal of the list will be over count will contain the count of the number of nodes in the linked list.<\/p>\n<\/li>\n The position of the middle node of the linked list will be given by (count\/2), store it in a variable mid.<\/p>\n<\/li>\n Now starting from the head of the linked list, traverse until the below condition holds:<\/p>\n At the end of the while loop, you will be at the node previous of the middle node. So now make head\u2192next = head\u2192next\u2192next to delete the middle node of the linked list.<\/p>\n<\/li>\n Finally, return Head_copy, which is the head of the newly formed list.<\/p>\n<\/li>\n<\/ul>\n Code Implementation to Delete Middle Element of Linked List (By Using the Naive Approach)<\/strong>![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/input-11.png\")
<\/p>\n![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/output-5.png\")
<\/p>\n
\nNow, in the above given linked list, 3rd node is the middle node of the linked list. Since we have to delete middle element of linked list, we remove the node containing 10 as the data. After deleting the node, we get the final linked list as given below.<\/p>\n![\"\"](\"https:\/\/prepbytes.com\/blog\/wp-content\/uploads\/2021\/08\/output-2-1.png\")
<\/p>\n\n
\n
\n
\nFor example, if the given linked list is 5\u219210\u219215\u219220\u219225, then 15 will be the middle node of the linked list, and we will remove this node from the linked list.
\nSo our final modified linked list after deletion will look like this 5\u219210\u219220\u219230.<\/p>\nNaive Approach to Delete the Middle Node of a Linked List<\/h3>\n
\nThe algorithm for the above-mentioned Approach is given below.<\/p>\n\n
while (mid-- > 1) {\n\nhead = head\u2192next;\n\n}<\/code><\/pre>\n<\/li>\n
\nThe code to delete middle element in linked list in C, C++, Java, and Python is given below.<\/p>\n\t\t\t\t\t\t