{x}
blog image

Delete the Middle Node of a Linked List

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

Solution Explanation: Delete the Middle Node of a Linked List

This problem requires deleting the middle node from a singly linked list. The "middle" node is defined as the floor(n/2)th node, where n is the number of nodes in the list. For example, in a list of 7 nodes, the middle node is the 3rd node (index 3).

Approach: Fast and Slow Pointers

The most efficient approach uses the fast and slow pointer technique. This technique leverages the relative speeds of two pointers traversing the list to identify the middle element.

  1. Initialization: We start with a dummy node prepended to the head. This simplifies handling edge cases (empty list or single-node list). A slow pointer (slow) starts at the dummy node, and a fast pointer (fast) starts at the head.

  2. Iteration: The fast pointer moves twice as fast as the slow pointer. In each iteration:

    • slow moves one step forward (slow = slow.next).
    • fast moves two steps forward (fast = fast.next.next).

  3. Termination: The loop continues until fast reaches the end of the list (i.e., fast or fast.next is null). At this point, slow will be pointing to the node before the middle node.

  4. Deletion: We delete the middle node by updating the next pointer of the slow node to skip over the middle node: slow.next = slow.next.next.

  5. Return: Finally, we return the next pointer of the dummy node (which is the head of the modified list).

Time and Space Complexity

  • Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list roughly once using the fast and slow pointers.
  • Space Complexity: O(1). We use only a constant number of extra variables (the pointers).

Code Implementation (Python)

# 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]:
        dummy = ListNode(next=head)  # Dummy node for easy handling of edge cases
        slow, fast = dummy, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        slow.next = slow.next.next  # Delete the middle node
        return dummy.next           # Return the head of the modified list

The code in other languages (Java, C++, Go, TypeScript) follows the same algorithm, just adapting the syntax to the respective language. The core logic remains identical, ensuring the same time and space complexity. The dummy node is crucial for handling edge cases elegantly without needing separate checks for empty or single-node lists.