Delete the Middle Node of a Linked List

Updated on 22 May, 2025
Delete the Middle Node of a Linked List header image

Problem Statement

In this problem, you are provided with the head of a singly linked list and your task is to remove the middle node from this list and return the head of the updated list. The middle node is defined on the basis of 0-based indexing; it is the node located at position ⌊n / 2⌋, where n is the total number of nodes in the list and ⌊x⌋ denotes the greatest integer less than or equal to x. The concept behind choosing ⌊n / 2⌋ is essentially picking the central node in an odd-numbered list and the first of the two middle nodes in an even-numbered list.

Examples

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

Approach and Intuition

The problem can be effectively approached by following these defined steps:

  1. Compute the size of the linked list. This involves traversing the list from the head to the end and counting the nodes.
  2. Determine the middle node's index using the formula ⌊n / 2⌋.
  3. If the list has only one node, simply return None because deleting the only node leaves the list empty.
  4. Traverse the list again up to the node just before the middle node. This is necessary because in singly linked lists, you can only remove a node if you have access to its predecessor.
  5. Adjust the next pointer of the node before the middle node (if it exists) to bypass the middle node, thereby removing it from the list.
  6. Return the head of the modified linked list.

From the given examples:

  • In example 1, list [1,3,4,7,1,2,6] has 7 nodes, thus the middle node is the one at index ⌊7/2⌋ = 3 (value 7). After removing node 7, the result is [1,3,4,1,2,6].
  • Example 2’s input list [1,2,3,4] has n = 4, so the middle is at index ⌊4/2⌋ = 2 (value 3). Post-removal, the list updates to [1,2,4].
  • With an input list of [2,1] in example 3, n = 2 puts the middle node at index 1 (value 1), and removing it leaves us with [2].

This method leverages straightforward list traversal techniques and provides an intuitive way to access and remove the middle node in a single pass through the list, followed by another partial pass to the determined middle index.

Solutions

  • C++
  • Java
  • JavaScript
cpp
class Solution {
public:
    ListNode* removeMiddleNode(ListNode* start) {
        if (start -> next == nullptr)
            return nullptr;
        
        ListNode *slowPointer = start, *fastPointer = start -> next -> next;
        
        while (fastPointer != nullptr && fastPointer -> next != nullptr) {
            slowPointer = slowPointer -> next;
            fastPointer = fastPointer -> next -> next;
        }
        
        slowPointer -> next = slowPointer -> next -> next;
        return start;
    }
};

This summary guides you through a C++ implementation designed to delete the middle node from a singly linked list. The goal is to return the modified linked list with one less node, specifically without the middle node.

  • The solution employs the two-pointer technique using a slowPointer and a fastPointer.
  • Begin by checking if the linked list is extremely short. If the start node's next points to nullptr, there's only one element, or the list is empty, in which case return nullptr.
  • Initialize slowPointer at the start node and fastPointer several steps ahead — specifically, at the second node's next if it exists. This sets up for the traversal where fastPointer will move twice as fast as slowPointer.
  • Traverse through the linked list:
    • Move slowPointer one step at a time.
    • Move fastPointer two steps at a time.
  • Continue this until fastPointer is either at the end of the list or has no further nodes (nullptr) to jump to.
  • Adjust the next pointer of the slowPointer to skip its next node (effectively removing the middle node since slowPointer would be just before the middle when fastPointer reaches the end).
  • Return the modified start of the linked list as the final result.

This method efficiently locates and removes the middle node in O(n) time with O(1) space complexity, utilizing a classic fast and slow pointer strategy.

java
class Solution {
    public ListNode removeMiddleNode(ListNode start) {
        if (start.next == null)
            return null;
        
        ListNode slow = start, fast = start.next.next;
        
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        
        slow.next = slow.next.next;
        return start;
    }
}

The solution provided addresses the problem of deleting the middle node from a linked list using Java. The approach implemented in the solution utilizes the two-pointer technique, consisting of "slow" and "fast" pointers, to determine the middle of the list efficiently.

Here's a breakdown of how the solution operates:

  1. Check if the start.next is null, indicating the list only contains one node. If true, return null as the list will be empty after removing the middle.

  2. Initialize two pointers, slow starting at the head of the list and fast starting at the second node's next node (two steps ahead).

  3. Iterate through the list while fast and fast.next are not null. Move slow one step for each two steps fast takes. When fast reaches the end of the list, slow will be exactly before the middle node of the linked list.

  4. Remove the middle element by setting slow.next to slow.next.next, effectively skipping over the middle node.

  5. Return the modified linked list starting from start.

This method ensures that the middle node is successfully removed while maintaining the integrity of the linked list, and it works efficiently with a time complexity of O(n), where n is the number of nodes in the list.

js
var removeMiddleNode = function(headNode) {
    if (headNode.next == null)
        return null;
    
    let slowPointer = headNode, fastPointer = headNode.next.next;
    
    while (fastPointer != null && fastPointer.next != null) {
        slowPointer = slowPointer.next;
        fastPointer = fastPointer.next.next;
    }
    
    slowPointer.next = slowPointer.next.next;
    return headNode;
};

The provided JavaScript function, removeMiddleNode, targets deleting the middle node from a singly linked list. Here's a breakdown of how the function operates:

  • Initially, it checks if the headNode has no following nodes by checking headNode.next. If this node is null, the function returns null, indicating the list was already empty or had only one element.
  • Two pointers, slowPointer and fastPointer, are used for traversal of the linked list. slowPointer progresses one node at a time, while fastPointer moves two nodes at a time. This difference allows slowPointer to reach the middle of the list when fastPointer reaches its end.
  • A loop continues until fastPointer either becomes null or has no next node, ensuring traversal to the end of the list. During each iteration, slowPointer and fastPointer are advanced accordingly.
  • Once the loop concludes, slowPointer directly links to the node after its next node (slowPointer.next = slowPointer.next.next), effectively skipping the middle node and removing it from the list.
  • Finally, the modified list with the middle node removed is returned by handing back the headNode.

This solution accomplishes the middle node removal efficiently by using the two-pointer technique to avoid counting or recalculating the list's length.

Comments

No comments yet.