Input: 1->2->3->4->5 

Output: 1->2->4->5

Explanation: Node with value 3 is at the middle node and deleted.

Input: 1->2->3->4

Output: 1->2->4

Explanation: The linked list has an even number of nodes hence we delete the second middle node which is 3.

Disclaimer: It's highly recommend trying to solve it before looking at the solution.

Brute Force Approach

Algorithm

Using the brute force approach, the middle node of a linked list can be determined by traversing the entire linked list initially to find the total number of nodes, denoted as n. Then we reset the temporary node temp to the head of the linked list and proceed to traverse to the node positioned at index [n/2], which represents either the middle node in an odd-lengthed list or the node just before the middle node in an even-lengthed linked list.

Traverse the linked list to count the number of nodes and store the length as n. Calculate the index of the middle node by dividing the total number of nodes by 2.

Traverse the linked list again while keeping track of the node count to reach the middle node.