# Delete Middle of linked list

The problem at hand involves deleting the middle node of a linked list. Given a singly linked list, we need to remove the middle node from it. The middle node refers to the node that is exactly in the middle of the linked list. If the linked list has an even number of nodes, there could be two middle nodes; however, we will remove only one of them.

## Problem Description

Given a singly linked list, the task is to remove the middle node from it. If the linked list has an odd number of nodes, there is a single middle node. If the linked list has an even number of nodes, there are two middle nodes, and we can remove either of them.

## Example

``7 -> 6 -> 5 -> 4 -> 3 -> 2 -> 1``

After removing the middle node, the linked list could become:

``7 -> 6 -> 5 -> 3 -> 2 -> 1``

Or:

``7 -> 6 -> 4 -> 3 -> 2 -> 1``

## Idea to Solve the Problem

After Delete Middle node

To solve this problem, we can use the slow and fast pointer approach. We use two pointers - a slow pointer and a fast pointer. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the linked list, the slow pointer will be at the middle node. We can then remove this middle node by updating the links.

## Pseudocode

``````deleteMiddle(linkedList):
return

prev = NULL

while fast is not NULL and fast.next is not NULL:
fast = fast.next.next
prev = slow
slow = slow.next

if prev is not NULL:
prev.next = slow.next
else:
#free(slow)``````

## Algorithm Explanation

1. Start with both the `slow` and `fast` pointers pointing to the head of the linked list, and initialize `prev` as NULL.
2. Traverse through the linked list using the `fast` pointer: a. Move the `fast` pointer by two steps and the `slow` pointer by one step. b. Keep track of the previous node using the `prev` pointer.
3. When the `fast` pointer reaches the end of the linked list, the `slow` pointer will be at the middle node.
4. Update the links to remove the middle node: a. If the `prev` pointer is not NULL, set `prev.next` to `slow.next`. b. If the `prev` pointer is NULL, update the head of the linked list to `slow.next`.
5. Free the memory occupied by the middle node.

## Time Complexity

The time complexity of this algorithm is O(n), where n is the number of nodes in the linked list. We traverse through the linked list once using the slow and fast pointers.

Note that in this linked list are 7 nodes. Then so 4'th position nodes is middle node of this linked list.

## Conclusion

This program are working when linked list contain at least three nodes. because if node are less than 3 then there are not possible to find mid node.

And linked list are contain even number of nodes. assuming there are more than two nodes. Then in this case there are possible two middle nodes. Let take an example.

`` 1-->2-->3-->4-->5-->6-->NULL ``

In this situation have 3rd and 4th position nodes are same priority of the mid position. So in this case both algorithm are valid to delete middle of 3rd position or 4th position nodes.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.