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 headI hope you got the idea about the problem and the solution concept.
Happy Learning.
Happy Coding.