# Delete Middle of the Linked List

Last updated: 29th Aug, 2020

#### Problem Statment

A singly linked list is given.The task is to delete middle of the linked list according to the given two conditions :
If there are odd number of nodes given : linked list is 1->2->3->4->5 then linked list should be modified to 1->2->4->5.
and If there are even nodes, then there would be two middle nodes, we need to delete the second middle element.
Given linked list is 1->2->3->4->5->6 then it should be modified to 1->2->3->5->6.
If the input linked list is NULL or has 1 node, then it should return NULL
Example 1:
Input Format
[1 -> 2 -> 3-> 4-> 5]
Output Format
[1 ->2 ->4 -> 5 ]
Example 2:
Input Format
[1 -> 2 -> 3-> 4-> 5 -> 6]
Output Format
[1 -> 2 -> 3-> 5 -> 6]

Approach:

1. There are three pointers (prev , i , j) which are initially initilized to None , head , head respectively.
2. At the beginning the i and j pointer will point the very first node
3. Check if j pointer and j.next pointer is valid
4. Then increase the j pointer to 2 steps ahead
5. Store the adress of i in prev pointer and increase i pointer to 1 step ahead.
6. Connect the address of prev pointer to the next address after i pointer.

###### Python Code

     def deleteMid(head):
        # check if the list contains 1 or more nodes
        if head is None or head.next is None:
            return None
        #assign pointers to their respective positions
        prev, i, j  = None, head, head

        while j and j.next:
            j = j.next.next;# j pointer moves 2 nodes ahead

            # update prev pointer , prev holds previous value of i pointer
            prev = i;

            # i pointer moves 1 node ahead
            i = i.next;

        #since i pointer was moving at half speed of j pointer , it points at
        # mid node when j pointer reaches the end
        prev.next = i.next; # bypassing mid node

        return head;

        # Driver's code
        class Node:
            def __init__(self,data):
                self.data = data
                self.next = None

        class Llist:
            def __init__(self):
                self.head = None

            def insert(self,data,link):
                node = Node (data)

                if not self.head:
                    self.head = node
                    return node
                link.next = node
                return node

            def printList(head):
                while head:
                    print(head.data, end=" ")
                    head = head.next
                print()

            if __name__ == "__main__":
                t = int (input())

                for x in range(t):
                    n = int(input())
                    arr1 = [int(y) for y in input().split()]
                    L1 = Llist()
                    link = None
                    for nodeData in arr1:
                        link = L1.insert (nodeData, link)
                        res = deleteMid(l1.head)
                        printList(res)