You are given the head of a linked list. Delete the middle node, and return the head of the modified linked list.

The middle node of a linked list of size n is the ⌊n / 2⌋th node from the start using 0-based indexing, where ⌊x⌋ denotes the largest integer less than or equal to x.

For n = 1, 2, 3, 4, and 5, the middle nodes are 0, 1, 1, 2, and 2, respectively.

Example 1:

Input: head = [1,3,4,7,1,2,6]
Output: [1,3,4,1,2,6]
Explanation:
The above figure represents the given linked list. The indices of the nodes are written below.
Since n = 7, node 3 with value 7 is the middle node, which is marked in red.
We return the new list after removing this node.

Example 2:

Input: head = [1,2,3,4]
Output: [1,2,4]
Explanation:
The above figure represents the given linked list.
For n = 4, node 2 with value 3 is the middle node, which is marked in red.

Example 3:

Input: head = [2,1]
Output: [2]
Explanation:
The above figure represents the given linked list.
For n = 2, node 1 with value 1 is the middle node, which is marked in red.
Node 0 with value 2 is the only node remaining after removing node 1.

Constraints:

The number of nodes in the list is in the range [1, 105].
1 <= Node.val <= 105

Explanation

Imagine your linked list is a train of connected cars. Each car has a value (the number inside) and a hook that connects it to the next car. The very first car is the “head” of the train.

Our goal is to find the middle car and remove it from the train.

Here’s how we do it, like a train inspector with special abilities:

🚃 Initial Setup:

You have your train (the linked list) starting with the “head” car.
You have two special inspectors: “Slow Inspector” and “Fast Inspector”.
Both inspectors start at the very first car (the head).
You also have a “Previous to Slow Inspector” who starts with no car in mind (or before the first car).

🚃 The Inspection Trip:

While the “Fast Inspector” can still move two steps forward (meaning there’s at least a car after the next one):
The “Previous to Slow Inspector” remembers the current car the “Slow Inspector” is on.
The “Slow Inspector” moves one car forward.
The “Fast Inspector” moves two cars forward.

🚃 Reaching the Middle:

When the “Fast Inspector” can no longer move two steps forward, it means we’ve reached (or passed) the end of the train.
At this point:
The “Slow Inspector” will be on the middle car of the train (if the train has an odd number of cars).
OR, the “Slow Inspector” will be on the second of the two middle cars (if the train has an even number of cars).
The “Previous to Slow Inspector” will be on the car just before the one the “Slow Inspector” is on.

🚃 Removing the Middle Car:

👉Special Case: The middle car is the very first car:

This happens if the train has only one car. In this case, you just disconnect the “head” — the train is now empty.

👉General Case: The middle car is somewhere in the middle:

Take the hook of the car that the “Previous to Slow Inspector” is on.
Instead of hooking it to the car the “Slow Inspector” is on (the middle car), hook it directly to the car after the one the “Slow Inspector” is on.
This effectively cuts the middle car out of the train.

🚃 The Result:

The train is now the same as before, but without the middle car. The “head” of the train remains the same (unless the middle car was the head).

Implementation

Python

# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def findMiddleAndBefore(self, head: Optional[ListNode]) -> tuple[Optional[ListNode], Optional[ListNode]]:
        """
        Finds the node just before the middle node and the middle node itself.

        Args:
            head: The head of the linked list.

        Returns:
            A tuple containing:
              - The node just before the middle node (None if the list has 0 or 1 nodes).
              - The middle node (or the second middle node if the list has an even number of nodes).
        """
        previous_slow = None
        slow = head
        fast = head

        while fast is not None and fast.next is not None:
            previous_slow = slow
            slow = slow.next
            fast = fast.next.next

        return previous_slow, slow

    def deleteMiddle(self, head: Optional[ListNode]) -> Optional[ListNode]:
        """
        Deletes the middle node of a singly linked list.

        Args:
            head: The head of the linked list.

        Returns:
            The head of the modified linked list. Returns None if the original list was empty.
        """
        # Handle base cases: empty list or list with only one node
        if not head:
            return None
        if not head.next:
            return None  # If only one node, after deleting the middle, it becomes empty

        # Find the node just before the middle and the middle node using the helper function
        one_before_middle, middle = self.findMiddleAndBefore(head)

        # Link the node before the middle to the node after the middle, effectively deleting the middle node
        one_before_middle.next = middle.next

        # Optionally, you could set middle.next to None to explicitly detach the deleted node
        # middle.next = None

        return head

Typescript

/**
 * Definition for singly-linked list.
 */
// class ListNode {
//     val: number;
//     next: ListNode | null;
//     constructor(val?: number, next?: ListNode | null) {
//         this.val = (val===undefined ? 0 : val);
//         this.next = (next===undefined ? null : next);
//     }
// }

function deleteMiddle(head: ListNode | null): ListNode | null {
    /**
     * Deletes the middle node of a singly linked list.
     *
     * Args:
     * head: The head of the linked list.
     *
     * Returns:
     * The head of the modified linked list. Returns null if the original list was empty.
     */
    if (!head) {
        return null;
    }
    if (!head.next) {
        return null; // If only one node, after deleting the middle, it becomes empty
    }

    let slow: ListNode | null = head;
    let fast: ListNode | null = head;
    let prev: ListNode | null = null;

    // Use fast and slow pointers to find the middle node
    while (fast !== null && fast.next !== null) {
        prev = slow;
        slow = slow!.next;
        fast = fast.next.next;
    }

    // 'slow' is now pointing to the middle node.
    // 'prev' is pointing to the node before the middle node.

    // If 'prev' is null, it means the middle node is the head (for a list of size 1, which we already handled,
    // or a list of size 2 where the first node is considered before the middle).
    // For a list of size 2 (e.g., 1 -> 2), slow will be 2, and prev will be 1. We want to remove slow.
    if (prev === null) {
        return head.next; // Middle node is the head
    }

    // Delete the middle node by linking the previous node to the next node of the middle node
    prev.next = slow!.next;

    return head;
};

Go

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 * Val int
 * Next *ListNode
 * }
 */

func deleteMiddle(head *ListNode) *ListNode {
 if head == nil {
  return nil
 }
 if head.Next == nil {
  return nil // If only one node, after deleting the middle, it becomes empty
 }

 slow := head
 fast := head
 var prev *ListNode

 // Use fast and slow pointers to find the middle node
 for fast != nil && fast.Next != nil {
  prev = slow
  slow = slow.Next
  fast = fast.Next.Next
 }

 // 'slow' is now pointing to the middle node.
 // 'prev' is pointing to the node before the middle node.

 // If 'prev' is nil, it means the middle node is the head (for a list of size 1, which we already handled,
 // or a list of size 2 where the first node is considered before the middle).
 // For a list of size 2 (e.g., 1 -> 2), slow will be 2, and prev will be 1. We want to remove slow.
 if prev == nil {
  return head.Next // Middle node is the head
 }

 // Delete the middle node by linking the previous node to the next node of the middle node
 prev.Next = slow.Next

 return head
}

If you liked this article I’d appreciate an upvote or a comment. That helps me improve the quality of my posts as well as getting to know more about you, my dear reader.

Muchas gracias!

Follow me for more content like this.

Down below you can find other ways to tip my work.

BankTransfer: "710969000019398639", // CLABE
BAT: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
ETH: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875",
BTC: "33xxUWU5kjcPk1Kr9ucn9tQXd2DbQ1b9tE",
ADA: "addr1q9l3y73e82hhwfr49eu0fkjw34w9s406wnln7rk9m4ky5fag8akgnwf3y4r2uzqf00rw0pvsucql0pqkzag5n450facq8vwr5e",
DOT: "1rRDzfMLPi88RixTeVc2beA5h2Q3z1K1Uk3kqqyej7nWPNf",
DOGE: "DRph8GEwGccvBWCe4wEQsWsTvQvsEH4QKH",
DAI: "0x33CD7770d3235F97e5A8a96D5F21766DbB08c875"

DSA (Medium) — Linked List — Delete the Middle Node of a Linked List (Python, Typescript & Go)

Explanation

Implementation

Python

Typescript

Go