Delete the Middle node of a Linked List

The above figure represents the given linked list. Since Number of Nodes = 7, node 3 with value 7 is the middle node, which is marked in red. We need to return the new list after removing this node. So the output will look like this

Pointer Placement

To solve this problem we will use the intuition from the previous problem Middle of the Linked List but slight differently. Instead of finding the middle node we will find the node Before the Middle Node. Let's visualize

# 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]:
		# dummy initialization and link with the HEAD
		dummy = ListNode(next=head) 
		slow = dummy
		fast = head

Find Node Before Middle Node

Since we need to find the node Before Mid, so Instead of placing both slow and fast at the HEAD we need to place the fast at the HEAD and slow pointer Before the HEAD. Then we will iterate over the list until the Fast reaches at the end of the list.

Notice carefully, for Linked List with Odd number of nodes, fast pointer will stop at the Last Node (i.e. before NULL) but for Linked List with Even number of nodes, fast pointer will stop at NULL

Now the slow pointer is before the middle node of the linked list. let's write the code.

	while fast and fast.next:
		slow = slow.next
		fast = fast.next.next
	
	# slow is now pointing at the node which is before the middle node
	node_before_mid = slow

This part of the code is Trivial which we have already seen in Middle of the Linked List problem. Main challenge was in pointer placement which is have done already. OK now Delete the Middle Node

Delete Middle Node

just a one liner: slow.next = slow.next.next

Complete Code Snippet

class Solution:
	def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
		# If there is only one node
		if not head.next:
			# after deleting that node the Linked List will be NULL
			return None
		
		# dummy initialization and link with the HEAD
		dummy = ListNode(next=head) 
		slow = dummy
		fast = head
		while fast and fast.next:
			slow = slow.next
			fast = fast.next.next
		# At this point slow is pointing the node before middle node
		# Just change the next pointer of the slow
		slow.next = slow.next.next
		return head

That's it, we are done. Thanks for stopping by!

Connect with me on