Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Delete the Middle Node of a Linked List

MEDIUMProblemSolveExternal Links

Description

You are given the head of a linked list. Your task is to delete the middle node of the list and return the head of the modified linked list.

The middle node is defined as the node at index ⌊n / 2⌋ using 0-based indexing, where n is the total number of nodes in the list and ⌊x⌋ denotes the floor function (the largest integer less than or equal to x).

For example:

  • If n = 1, the middle node is at index 0 (the only node)
  • If n = 2, the middle node is at index 1 (the second node)
  • If n = 3, the middle node is at index 1 (the second node)
  • If n = 4, the middle node is at index 2 (the third node)
  • If n = 5, the middle node is at index 2 (the third node)

Examples

Example 1

Input: head = [1, 3, 4, 7, 1, 2, 6]

Output: [1, 3, 4, 1, 2, 6]

Explanation: The list has n = 7 nodes. The middle index is ⌊7 / 2⌋ = 3 (0-based). The node at index 3 has value 7. After removing node 7, the list becomes [1, 3, 4, 1, 2, 6].

Example 2

Input: head = [1, 2, 3, 4]

Output: [1, 2, 4]

Explanation: The list has n = 4 nodes. The middle index is ⌊4 / 2⌋ = 2 (0-based). The node at index 2 has value 3. After removing it, the list becomes [1, 2, 4].

Example 3

Input: head = [2, 1]

Output: [2]

Explanation: The list has n = 2 nodes. The middle index is ⌊2 / 2⌋ = 1 (0-based). The node at index 1 has value 1. After removing it, the list becomes [2].

Example 4

Input: head = [5]

Output: []

Explanation: The list has n = 1 node. The middle index is ⌊1 / 2⌋ = 0 (0-based). The only node is the middle node. After removing it, the list is empty.

Constraints

  • The number of nodes in the list is in the range [1, 10^5]
  • 1 ≤ Node.val ≤ 10^5

Editorial

Brute Force

Intuition

The most straightforward way to delete the middle node is a two-step process: first figure out where the middle is, then go back and remove it.

Imagine you are standing in a hallway with a row of numbered doors (0, 1, 2, ...). Someone tells you to remove the door in the middle, but you do not know how many doors there are. Your natural approach would be to walk all the way down the hallway, count the doors (say you count 7), calculate the middle position (⌊7/2⌋ = 3), then walk back to door number 3 and remove it.

We do the same with the linked list: traverse it once to count the total nodes, compute the middle index, then traverse again stopping just before the middle node so we can bypass it by updating the previous node's pointer.

Step-by-Step Explanation

Let's trace through with head = [1, 3, 4, 7, 1, 2, 6]:

Pass 1 — Count nodes:

Step 1: Start at head, count = 0. Visit node(1), count = 1.

Step 2: Visit node(3), count = 2.

Step 3: Visit node(4), count = 3.

Step 4: Visit node(7), count = 4.

Step 5: Visit node(1), count = 5.

Step 6: Visit node(2), count = 6.

Step 7: Visit node(6), count = 7. End of list. Total n = 7.

Step 8: Compute middle index = ⌊7 / 2⌋ = 3. We need to delete the node at index 3 (value 7).

Pass 2 — Navigate to position (middle - 1) and delete:

Step 9: Start at head (index 0). We need to reach index 2 (one before middle).

Step 10: Move to index 1 (node with value 3).

Step 11: Move to index 2 (node with value 4). This is the node just before the middle.

Step 12: Bypass the middle: set node(4).next = node(4).next.next. This skips node(7) and connects node(4) directly to node(1).

Result: The list is now [1, 3, 4, 1, 2, 6].

Brute Force — Two-Pass Count and Delete — Watch the two-pass approach: first we count all nodes to find the total length, then we traverse again to the node just before the middle and bypass it.

Algorithm

  1. If the list has only one node, return null (the only node is the middle)
  2. Pass 1 — Count: Traverse the entire list to count the number of nodes n
  3. Compute the middle index: middleIndex = ⌊n / 2⌋
  4. Pass 2 — Delete: Traverse the list again, stopping at the node at index (middleIndex - 1)
  5. Bypass the middle node: set the previous node's next pointer to skip over the middle node (prev.next = prev.next.next)
  6. Return the head of the modified list

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (!head->next) return nullptr;
        
        // Pass 1: Count total nodes
        int count = 0;
        ListNode* curr = head;
        while (curr) {
            count++;
            curr = curr->next;
        }
        
        int middleIndex = count / 2;
        
        // Pass 2: Navigate to node before middle
        curr = head;
        for (int i = 0; i < middleIndex - 1; i++) {
            curr = curr->next;
        }
        
        // Bypass middle node
        curr->next = curr->next->next;
        
        return head;
    }
};
# 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 not head.next:
            return None
        
        # Pass 1: Count total nodes
        count = 0
        curr = head
        while curr:
            count += 1
            curr = curr.next
        
        middle_index = count // 2
        
        # Pass 2: Navigate to node before middle
        curr = head
        for i in range(middle_index - 1):
            curr = curr.next
        
        # Bypass middle node
        curr.next = curr.next.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; }
 * }
 */
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head.next == null) return null;
        
        // Pass 1: Count total nodes
        int count = 0;
        ListNode curr = head;
        while (curr != null) {
            count++;
            curr = curr.next;
        }
        
        int middleIndex = count / 2;
        
        // Pass 2: Navigate to node before middle
        curr = head;
        for (int i = 0; i < middleIndex - 1; i++) {
            curr = curr.next;
        }
        
        // Bypass middle node
        curr.next = curr.next.next;
        
        return head;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the linked list twice. The first pass visits all n nodes to count them. The second pass visits up to n/2 nodes to reach the position before the middle. The total work is O(n) + O(n/2) = O(n).

Space Complexity: O(1)

We use only a few variables (count, middleIndex, curr) which do not grow with the input size. No additional data structures are needed.

Why This Approach Is Not Efficient

While the brute force approach correctly solves the problem in O(n) time and O(1) space, it requires two separate traversals of the linked list. The first traversal counts the nodes, and the second traversal navigates to the deletion point.

The core inefficiency is that we visit the first half of the list twice — once during counting and once during navigation. We are doing redundant work because we cannot determine the middle position during the first pass.

The key insight is that we can find the middle of a linked list in a single pass using the slow-fast pointer technique (also called the tortoise and hare approach). If we move one pointer at speed 1 (one node per step) and another pointer at speed 2 (two nodes per step), when the fast pointer reaches the end, the slow pointer will be exactly at the middle. This eliminates the need for a separate counting pass.

Optimal Approach - Slow and Fast Pointers

Intuition

Instead of counting nodes first, we can find the middle in a single traversal using the slow-fast pointer trick.

Imagine two runners on a track. Runner A runs at normal speed (1 step at a time), and Runner B runs at double speed (2 steps at a time). They both start at the beginning. When Runner B reaches the finish line, Runner A will be exactly at the halfway point — because Runner A has covered half the distance that Runner B covered.

We apply this same idea to the linked list:

  • A slow pointer moves one node at a time
  • A fast pointer moves two nodes at a time
  • When the fast pointer reaches the end (or goes past it), the slow pointer is at the middle

Since we need to delete the middle node, we actually want to stop the slow pointer one node before the middle. We do this by keeping a prev pointer that trails one step behind the slow pointer (or equivalently, starting the fast pointer two steps ahead). When we find the middle, we simply set prev.next = slow.next to bypass it.

Step-by-Step Explanation

Let's trace through with head = [1, 3, 4, 7, 1, 2, 6]:

Step 1: Initialize slow = head (node 1, index 0), fast = head.next.next (node 4, index 2). We start fast two steps ahead so that when fast reaches the end, slow will be one node before the middle.

Step 2: Move slow one step: slow → node(3) at index 1. Move fast two steps: fast → node(1) at index 4.

  • Slow at index 1, fast at index 4. Fast hasn't reached the end yet.

Step 3: Move slow one step: slow → node(4) at index 2. Move fast two steps: fast → node(6) at index 6.

  • Slow at index 2, fast at index 6. Fast is at the last node.

Step 4: Check loop condition: fast.next is null, so we stop. Slow is at index 2 (value 4), which is one node before the middle (index 3, value 7).

Step 5: Delete the middle: slow.next = slow.next.next. Node(4)'s next now points to node(1) at index 4, skipping node(7).

Result: The list becomes [1, 3, 4, 1, 2, 6]. We found and deleted the middle in a single pass.

Slow-Fast Pointer — Single-Pass Middle Deletion — Watch how the slow pointer moves at half the speed of the fast pointer. When fast reaches the end, slow is perfectly positioned one node before the middle, ready to delete it.

Algorithm

  1. If the list has only one node, return null (the only node is the middle)
  2. Initialize:
    • slow = head (will end up one node before the middle)
    • fast = head.next.next (starts two steps ahead of slow)
  3. While fast is not null AND fast.next is not null:
    • Move slow forward by one node: slow = slow.next
    • Move fast forward by two nodes: fast = fast.next.next
  4. When the loop ends, slow is at the node just before the middle
  5. Delete the middle node: slow.next = slow.next.next
  6. Return head

Code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (!head->next) return nullptr;
        
        ListNode* slow = head;
        ListNode* fast = head->next->next;
        
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        
        // slow is now one node before the middle
        slow->next = slow->next->next;
        
        return head;
    }
};
# 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 not head.next:
            return None
        
        slow = head
        fast = head.next.next
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        
        # slow is now one node before the middle
        slow.next = slow.next.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; }
 * }
 */
class Solution {
    public ListNode deleteMiddle(ListNode head) {
        if (head.next == null) return null;
        
        ListNode slow = head;
        ListNode fast = head.next.next;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        // slow is now one node before the middle
        slow.next = slow.next.next;
        
        return head;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the linked list exactly once. The fast pointer moves through the list at double speed, so the loop runs approximately n/2 times. Each iteration does constant work (two pointer advances). Total time: O(n/2) = O(n).

Compared to the brute force which also takes O(n) time, the optimal approach performs roughly half as many node visits because it eliminates the redundant counting pass.

Space Complexity: O(1)

We use only two extra pointers (slow and fast) regardless of the input size. No additional data structures or arrays are needed. The deletion is performed entirely in-place by re-linking one pointer.