2095. Delete the Middle Node of a Linked List

Linked List
Two Pointers

TIME

O(n)

SPACE

O(1)

Intuition

To delete a node from a singly linked list we need the node before it. Finding the middle in one pass is the classic slow/fast pointer trick: advance fast by two and slow by one, so when fast reaches the end, slow is at the middle. We just also keep a prev pointer trailing slow so we can splice the middle out.

For ⌊n/2⌋ 0-indexed, starting both pointers at the head and stepping while fast and fast.next exist lands slow exactly on the node to delete.

Approach

Handle the single-node case up front: deleting index 0 leaves an empty list, so return None.
Walk slow (with prev behind it) one step and fast two steps until fast runs off the end.
slow now points at the middle node; unlink it with prev.next = slow.next.
Return head.

Complexity

Time: O(n), single traversal
Space: O(1), only a few pointers

Edge Cases

Single node -> result is an empty list (None)
Two nodes -> middle is index 1, leaving only the head
Odd vs even length -> the fast/fast.next loop condition picks ⌊n/2⌋ in both cases

Code

from typing import Optional


# 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"]:
        """
        2095. Delete the Middle Node of a Linked List
        Time: O(n)
        Space: O(1)
        """
        if head is None or head.next is None:
            return None

        prev = None
        slow, fast = head, head

        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next

        # slow is the middle node; splice it out.
        prev.next = slow.next
        return head

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

/**
 * 2095. Delete the Middle Node of a Linked List
 * Time: O(n)
 * Space: O(1)
 */
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }

        ListNode prev = null;
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            prev = slow;
            slow = slow.next;
            fast = fast.next.next;
        }

        // slow is the middle node; splice it out.
        prev.next = slow.next;
        return head;
    }
}