You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.


	For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.


&nbsp;
Example 1:

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node. 


Example 2:

Input: head = [1,2,3,4]
Output: [1,2,4]
Explanation:
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.


Example 3:

Input: head = [2,1]
Output: [2]
Explanation:
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

&nbsp;
Constraints:


	The number of nodes in the list is in the range [1, 105].
	1 &lt;= Node.val &lt;= 105


# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
  def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    if not head: return head
    if head and not head.next: return None

    prev = ListNode(0, head)
    slow = fast = head
    while fast and fast.next:
      prev = slow
      slow = slow.next
      fast = fast.next.next

    prev.next = slow.next
    return head
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        // Base Condition
        if(head == null || head.next == null) return null;
        // Pointers Created
        ListNode fast = head;
        ListNode slow = head;
        ListNode prev = head;

        while(fast != null && fast.next != null){
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        prev.next = slow.next;
        return head;
    }
}
**Intution**- we know that we can find middle node using two pointer fast and slow. 
 After we iterate through linkedlist slow pointer is our middle node and since we need to delete it
 we only need pointer to its previous node and then just simply put next to next node in previous node.
 Woahh ! you are done with deleting middle NODE;

class Solution {
public:
	ListNode* deleteMiddle(ListNode* head) {
		   if(head->next==nullptr) return nullptr;
		   ListNode *f=head;
		   ListNode *s=head,*prev;
		  while(f!=nullptr && f->next!=nullptr){
			  f=f->next->next;
			  prev=s;
			  s=s->next;
		  }
		prev->next=prev->next->next;
		return head;
	}
};
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 * this.val = (val===undefined ? 0 : val)
 * this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
// Two Pointer: Fast & Slow | O(N) | O(1)
var deleteMiddle = function(head) {
  if (!head.next) return null;

  let prev = head;
  let slow = head;
  let fast = head.next;
  let size = 2;

  while (fast && fast.next) {
    prev = slow;
    slow = slow.next;
    fast = fast.next.next;
    size += fast ? 2 : 1;
  }

  if (size % 2 === 0) slow.next = slow.next.next;
  else prev.next = slow.next;

  return head;
};
Delete the Middle Node of a Linked List