Given a linked list, remove the middle node. This one’s pretty straightforward. Using a fast and slow pointer, we traverse the list with the fast pointer until the slow pointer reaches the middle. We also maintain the previous node, the node before the slow pointer.
Once we reach the middle, we point the previous node the the node after the slow pointer and return the head.
The solution is as follows:
class Solution:
def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev, slow, fast = None, head, head.next
while fast:
fast = fast.next
if fast:
fast = fast.next
prev = slow
slow = slow.next
if not prev:
return prev
prev.next = slow.next
return head_ Time Complexity:
O(n) - We traverse all nodes within the linked list.
_ Space Complexity:
O(1) - We maintain pointers that occupy constant space.