Delete the Middle Node of a Linked List - Practice Coding Problems

Delete the Middle Node of a Linked List - Problem

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.

Input & Output

Example 1 — Odd Length List

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

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

💡 Note: List has 7 nodes. Middle is at index ⌊7/2⌋ = 3 (value 7). After deletion: [1,3,4,1,2,6]

Example 2 — Even Length List

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

› Output: [1,2,4]

💡 Note: List has 4 nodes. Middle is at index ⌊4/2⌋ = 2 (value 3). After deletion: [1,2,4]

Example 3 — Two Nodes

$ Input: head = [2,1]

› Output: [1]

💡 Note: List has 2 nodes. Middle is at index ⌊2/2⌋ = 1 (value 1). After deletion: [1] - wait, that's wrong. Middle should be index 1, so delete node with value 1, leaving [2]. Actually, for n=2, middle index is 1, so we delete the second node, leaving [2].

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input List

Original linked list [1,3,4,7,1,2,6] with 7 nodes

Find Middle

Middle position is ⌊7/2⌋ = 3, which contains value 7

Delete Middle

Remove middle node, resulting in [1,3,4,1,2,6]

Key Takeaway

🎯 Key Insight: Use fast-slow pointers to find the middle node in one pass - when fast reaches the end, slow is at the right position to delete the middle

Asked in

M Microsoft 25 a Amazon 18 G Google 15 f Meta 12

The optimal approach uses two pointers moving at different speeds to find the middle node in a single pass. The fast pointer moves 2 steps while the slow pointer moves 1 step. When the fast pointer reaches the end, the slow pointer will be just before the middle node, allowing us to delete it efficiently. Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Two-Pass Approach	O(n)	O(1)	Count nodes first, then traverse again to delete middle
Fast-Slow Pointer (Optimal)	O(n)	O(1)	Use fast and slow pointers to find middle in one pass

Two-Pass Approach — Algorithm Steps

Step 1: Count total nodes in the linked list
Step 2: Calculate middle position ⌊n/2⌋
Step 3: Traverse to position before middle and delete

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Nodes

First pass counts all nodes

Find Middle

Calculate middle position ⌊n/2⌋

Delete Middle

Second pass removes the middle node

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct ListNode {
    int val;
    struct ListNode* next;
};

struct ListNode* solution(struct ListNode* head) {
    if (!head || !head->next) {
        return NULL;
    }
    
    // First pass: count nodes
    int count = 0;
    struct ListNode* current = head;
    while (current) {
        count++;
        current = current->next;
    }
    
    // Find middle position
    int middlePos = count / 2;
    
    // Second pass: delete middle node
    current = head;
    for (int i = 0; i < middlePos - 1; i++) {
        current = current->next;
    }
    
    current->next = current->next->next;
    return head;
}

struct ListNode* createNode(int val) {
    struct ListNode* node = (struct ListNode*)malloc(sizeof(struct ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}

void printList(struct ListNode* head) {
    printf("[");
    struct ListNode* current = head;
    int first = 1;
    while (current) {
        if (!first) printf(",");
        printf("%d", current->val);
        first = 0;
        current = current->next;
    }
    printf("]\n");
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for [1,2,3,4,5] format
    struct ListNode* head = NULL;
    struct ListNode* tail = NULL;
    
    char* ptr = strchr(line, '[');
    if (ptr) {
        ptr++;
        char* token = strtok(ptr, ",]");
        while (token) {
            int val = atoi(token);
            struct ListNode* node = createNode(val);
            if (!head) {
                head = tail = node;
            } else {
                tail->next = node;
                tail = node;
            }
            token = strtok(NULL, ",]");
        }
    }
    
    struct ListNode* result = solution(head);
    printList(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Two passes through the linked list: O(n) + O(n) = O(n)

✓ Linear Growth

Space Complexity

O(1)

Only uses a few variables, no extra data structures

✓ Linear Space

145.6K Views

Medium Frequency

~15 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Two-Pass Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler