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)