Delete the Middle Node of a Linked List | LeetCode 2095 | Python | Solution

LeetCode 2095

Before moving into the problem, we need to know how to delete a node from a linked list. If you don’t know about Linked List, you can read my article about it (Linked List).

To delete a node, we need to keep track previous node of it. We will use the formula: previous.next = delete.next. Then it will detach from the linked list.
If there is only one (head) node, we will return None (null). Because the head is the middle node this time, and if we delete it, the linked list will be empty.

To delete the middle node of a linked list, first, we have to find that node from a list. For that, we will use two-pointers and name those slow and fast. Slow pointer traverses through the list one step each time, and fast one will two steps each time. This iteration will continue until the fast one reaches the end of the list. And at that time, the slow one will point to the middle node of the list.

If a linked list has two middle nodes, the slow pointer will point to the second node. You can check it using a simple example. And this is what we need to solve this problem.

Middle of the Linked List – LeetCode Soution

When we have access to the middle node, we can delete it from the given linked list.

Let’s see the solution for better understanding.

# 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]:
        
        
        if head.next is None:
            return None
        
        slow = fast = head
        prev_node = None
        
        
        while fast and fast.next:
            prev_node = slow
            
            slow = slow.next
            fast = fast.next.next
        
        
        prev_node.next = slow.next
        
        return head

I hope you got the idea about the problem and the solution concept.

Happy Learning.
Happy Coding.

Scroll to Top