Python Program To Delete Middle Of Linked List
Given a singly linked list, delete the middle of the linked list. For example, if the given linked list is 1->2->3->4->5 then the linked list should be modified to 1->2->4->5
If there are even nodes, then there would be two middle nodes, we need to delete the second middle element. For example, if 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, then it should remain NULL.
If the input linked list has 1 node, then this node should be deleted and a new head should be returned.
Simple solution: The idea is to first count the number of nodes in a linked list, then delete n/2’th node using the simple deletion process.
Python3
# Python3 program to delete middle # of a linked list # Link list Node class Node: def __init__( self ): self .data = 0 self . next = None # Count of nodes def countOfNodes(head): count = 0 while (head ! = None ): head = head. next count + = 1 return count # Deletes middle node and returns # head of the modified list def deleteMid(head): # Base cases if (head = = None ): return None if (head. next = = None ): del head return None copyHead = head # Find the count of nodes count = countOfNodes(head) # Find the middle node mid = count / / 2 # Delete the middle node while (mid > 1 ): mid - = 1 head = head. next # Delete the middle node head. next = head. next . next return copyHead # A utility function to print # a given linked list def printList(ptr): while (ptr ! = None ): print (ptr.data, end = '->' ) ptr = ptr. next print ( 'NULL' ) # Utility function to create # a new node. def newNode(data): temp = Node() temp.data = data temp. next = None return temp # Driver Code if __name__ = = '__main__' : # Start with the empty list head = newNode( 1 ) head. next = newNode( 2 ) head. next . next = newNode( 3 ) head. next . next . next = newNode( 4 ) print ( "Given Linked List" ) printList(head) head = deleteMid(head) print ( "Linked List after deletion of middle" ) printList(head) # This code is contributed by rutvik_56 |
Output:
Given Linked List 1->2->3->4->NULL Linked List after deletion of middle 1->2->4->NULL
Complexity Analysis:
- Time Complexity: O(n).
Two traversals of the linked list is needed - Auxiliary Space: O(1).
No extra space is needed.
Efficient solution:
Approach: The above solution requires two traversals of the linked list. The middle node can be deleted using one traversal. The idea is to use two pointers, slow_ptr, and fast_ptr. Both pointers start from the head of list. When fast_ptr reaches the end, slow_ptr reaches middle. This idea is same as the one used in method 2 of this post. The additional thing in this post is to keep track of the previous middle so the middle node can be deleted.
Below is the implementation.
Python3
# Python3 program to delete the # middle of a linked list # Linked List Node class Node: def __init__( self , data): self .data = data self . next = None # Create and handle list # operations class LinkedList: def __init__( self ): # Head of the list self .head = None # Add new node to the list end def addToList( self , data): newNode = Node(data) if self .head is None : self .head = newNode return last = self .head while last. next : last = last. next last. next = newNode # Returns the list in string # format def __str__( self ): linkedListStr = "" temp = self .head while temp: linkedListStr + = str (temp.data) + "->" temp = temp. next return linkedListStr + "NULL" # Method deletes middle node def deleteMid( self ): # Base cases if ( self .head is None or self .head. next is None ): return # Initialize slow and fast pointers # to reach middle of linked list slow_Ptr = self .head fast_Ptr = self .head # Find the middle and previous of # middle prev = None # To store previous of slow pointer while (fast_Ptr is not None and fast_Ptr. next is not None ): fast_Ptr = fast_Ptr. next . next prev = slow_Ptr slow_Ptr = slow_Ptr. next # Delete the middle node prev. next = slow_Ptr. next # Driver code linkedList = LinkedList() linkedList.addToList( 1 ) linkedList.addToList( 2 ) linkedList.addToList( 3 ) linkedList.addToList( 4 ) print ( "Given Linked List" ) print (linkedList) linkedList.deleteMid() print ( "Linked List after deletion of middle" ) print (linkedList) # This code is contributed by Debidutta Rath |
Output:
Given Linked List 1->2->3->4->NULL Linked List after deletion of middle 1->2->4->NULL
Complexity Analysis:
- Time Complexity: O(n).
Only one traversal of the linked list is needed - Auxiliary Space: O(1).
As no extra space is needed.
Please refer complete article on Delete middle of linked list for more details!