Delete Middle Node

The idea is simple and naive. We will first count the total number of nodes in the linked list (say ‘N’). Now, we know that the ceil('N' / 2)^th node is our middle node of the linked list. 

So, now we will follow the traditional algorithm for deleting a node from the linked list. We will traverse till the previous node of the node which is going to be deleted, and point the next pointer of the previous node to the next node of the middle node. Also, we will save the pointer to the middle node to deallocate the memory. In simple words:

• 'PREV_NODE' -> next = ‘MIDDLE_NODE’ -> next.
• delete 'MIDDLE_NODE’

The idea here is to use two pointers i.e. ‘SLOW’ and ‘FAST’ and both will traverse in the linked list from beginning to end but at a different pace. The ‘SLOW’ pointer will move normally in the linked list, one step at a time. The other ‘FAST’ pointer will move two steps at a time. 

Now, when the ‘FAST’ pointer reaches the end of the list, we know that the ‘SLOW’ pointer is only halfway through because the speed is half for the ‘SLOW’ pointer. Hence, the ‘SLOW’ pointer must be standing at the middle node, so we delete it. 

As mentioned earlier, we will be using the traditional method of deleting the node from the list which is to have a pointer to the previous node of the node which is going to be deleted. Also, we will save the pointer to the middle node to deallocate the memory. For that, we can maintain a different pointer ‘PREVIOUS’ which will be used to track the previous node of the ‘SLOW’ pointer. In simple words:

• 'PREVIOUS' -> next = 'SLOW' -> next
• delete 'SLOW'