How do you delete a middle node in a singly linked list in Python?

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

Table of Contents Show

Delete middle of linked list
Python Program To Delete Middle Of Linked List
6. Python program to delete a node from the middle of the Circular Linked List
About Linked List
Delete middle node from linked list in python

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.

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 the input linked list has 1 node, then this node should be deleted and a new head should be returned.

Recommended: Please solve it on “PRACTICE” first, before moving on to the solution.

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!

Article Tags :

Linked List

Python Programs

Flipkart

Microsoft

Tortoise-Hare-Approach

Practice Tags :

Flipkart

Microsoft

Linked List

Read Full Article

6. Python program to delete a node from the middle of the Circular Linked List

In this program, we will create a circular linked list and delete a node from the middle of the list. If the list is empty, display the message "List is empty". If the list is not empty, we will calculate the size of the list and then divide it by 2 to get the mid-point of the list. We maintain two pointers temp and current. Current will point to the previous node of temp. We will iterate through the list until mid-point is reached then the current will point to the middle node. We delete middle node such that current's next will be temp's next node.

Circular linked list after deleting the node from the middle of the list

Consider the above list. Size of the list is 4. Mid-point of the node is 2. To remove C from the list, we will iterate through the list till mid-point. Now current will point to B and temp will point to C. C will be removed when B will point to D.

ALGORITHM:

Define a Node class which represents a node in the list. It has two properties data and next which will point to the next node.
Define another class for creating the circular linked list, and it has two nodes: head and tail. It has a variable size and two methods: deleteMid() and display() .
deleteMid() will delete the node from the middle of the list:

It first checks whether the head is null (empty list) then, it will return from the function as there is no node present in the list.
If the list is not empty, it will check whether the list has only one node.
If the list has only one node, it will set both head and tail to null.
If the list has more than one node then, it will calculate the size of the list. Divide the size by 2 and store it in the variable count.
Temp will point to head, and current will point to the previous node to temp.
Iterate the list till current will point middle node of the list.
Current will point to node next to temp, i.e., removes the node next to current.

a. display() will show all the nodes present in the list.

Define a new node 'current' that will point to the head.
Print current.data till current will points to head again.
Current will point to the next node in the list in each iteration.

PROGRAM:

Output:

Original List: 1 2 3 4 Updated List: 1 3 4 Updated List: 1 4 Updated List: 4 Updated List: List is empty

About Linked List

Linked List is a one of the DataStructure used for storing collection of data. A Linked List has the following properties:

A Linked List is linear dynamic DataStructure.
The number of nodes in Linked List is not fixed, it can grow and shrink on demand.
Each node of the Linked List is made up of two items - the data and a reference to the next node.
The Last node has reference to null.
The entry point is called head
If the list is empty then the head is null reference.

Basic Structure of Linked List-

Delete middle node from linked list in python

Python program for Delete middle node from linked list. Here problem description and explanation.

# Python 3 program for # Delete middle node of linked list # Linked list node class LinkNode : def __init__(self, data) : self.data = data self.next = None class SingleLL : def __init__(self) : self.head = None # Adding new node at beginning of linked list def addNode(self, data) : # Create new node node = LinkNode(data) # Connect current node to previous head node.next = self.head self.head = node # Display linked list element def display(self) : if (self.head == None) : return temp = self.head # iterating linked list elements while (temp != None) : # Display node value print(temp.data, end = " → ") # Visit to next node temp = temp.next print(" NULL") # Delete the middle node of linked list def deleteMid(self) : if (self.head == None) : # When linked list are no elements print("Empty Linked List") elif (self.head.next == None and self.head.next.next == None) : # When linked list are less than of 3 nodes print("Less then 3 node of linked list") else : temp = self.head midPrevious = None # Find the middle and its previous node while (temp != None and temp.next != None and temp.next.next != None) : if (midPrevious == None) : # When first node midPrevious = temp else : # Visit to next node midPrevious = midPrevious.next # Visit to next second next node temp = temp.next.next # Get the node which is deleting temp = midPrevious.next # Show deleted node print("Delete node : ", temp.data) # Change link midPrevious.next = temp.next def main() : sll = SingleLL() # Linked list # 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL sll.addNode(1) sll.addNode(2) sll.addNode(3) sll.addNode(4) sll.addNode(5) sll.addNode(6) sll.addNode(7) print("Before Delete middle node") sll.display() # Delete middle node sll.deleteMid() print("After Delete middle node") sll.display() if __name__ == "__main__": main()

Output

Before Delete middle node 7 → 6 → 5 → 4 → 3 → 2 → 1 → NULL Delete node : 4 After Delete middle node 7 → 6 → 5 → 3 → 2 → 1 → NULL