2095. Delete the Middle Node of a Linked List

Description

The problem requires deleting the middle node of a singly linked list. If the list has an even number of nodes, the function should delete the second of the two middle nodes. The task is to return the head of the modified list after the middle node has been removed. If the list is empty or has only one node, the function should return null or None.

Intuition

To find the middle of the list efficiently, the fast and slow pointer approach is used. The slow pointer moves one step at a time while the fast pointer moves two steps at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle node. Once the middle node is found, it can be removed by adjusting the next pointer of the previous node.

Approach

1. Edge Case Handling: If the list is empty or contains only one node, return null or None because there's no middle node to delete.
2. Initialize Pointers: Use two pointers, slow and fast, both starting at the head of the list. The fast pointer should move twice as fast as the slow pointer.
3. Find the Middle Node: Move the slow pointer one step at a time and the fast pointer two steps at a time. Stop when the fast pointer cannot proceed further.
4. Delete the Middle Node: When the fast pointer reaches the end of the list, the slow pointer will be at the middle node. Adjust the next pointer of the node before the slow pointer to skip the middle node, effectively removing it from the list.
5. Return the Modified List: After the middle node is removed, return the head of the list.

Complexity

Time Complexity:

The algorithm runs in O(n) time, where n is the number of nodes in the list. This is because the list is traversed once.

Space Complexity:

The algorithm uses O(1) extra space, as only a few pointers are used, and no additional data structures are needed.

Code

C++

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (!head || !head->next) {
            return nullptr;
        }
        ListNode *slow = head, *fast = head;
        fast = fast->next->next;
        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};

Python

class Solution:
    def deleteMiddle(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return None
        slow, fast = head, head
        fast = fast.next.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        slow.next = slow.next.next
        return head

Java

class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        ListNode slow = head, fast = head;
        fast = fast.next.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

JavaScript

var deleteMiddle = function (head) {
    
    if (!head || !head.next) {
        return null
    }
    let slow = head, fast = head
    fast = fast.next.next
    while (fast !== null && fast.next !== null) {
        slow = slow.next
        fast = fast.next.next
    }
    slow.next = slow.next.next
    return head
};