We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Delete the Middle Node of a Linked List

Number: 2216

Difficulty: Medium

Paid? No

Companies: Amazon, Bloomberg, Google, Meta, Adobe

Problem Description

Given the head of a singly linked list, remove the middle node and return the head of the modified list. The middle node is defined as the ⌊n / 2⌋th node (0-indexed) in a list of n nodes. For example, in a list of 7 nodes, the 3rd node (0-indexed) is the middle node to remove. In the case where the list only contains one node, removing the middle node results in an empty list.

Key Insights

  • Use the two pointers technique (slow and fast pointers) to find the middle node in a single pass.
  • Track the node previous to the slow pointer node to efficiently remove the middle node by changing the 'next' pointer.
  • Handle the edge case when the list contains only one node, in which case the result is an empty list.

Space and Time Complexity

Time Complexity: O(n) because we traverse the list once. Space Complexity: O(1) as only a constant amount of extra space is used.

Solution

We use the two pointers technique where the slow pointer moves one step at a time while the fast pointer moves two steps. When the fast pointer reaches the end, the slow pointer will be at the middle node. We also maintain a pointer to the previous node of the slow pointer so we can remove the middle node by linking the previous node directly to the next node of the slow pointer. If the list only has one node, we return null since the single node is the middle node to be removed.

Code Solutions

# 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: ListNode) -> ListNode:
        # If the list is empty or contains only one node, return None
        if not head or not head.next:
            return None
        
        # Initialize two pointers for the two-pointer approach
        slow = head             # slow pointer starts at head
        fast = head             # fast pointer starts at head
        prev = None             # previous pointer to track node before slow
        
        # Traverse the list until fast reaches the end
        while fast and fast.next:
            prev = slow         # keep track of the node before slow
            slow = slow.next    # move slow by one step
            fast = fast.next.next  # move fast by two steps
        
        # Now, slow is at the middle node.
        # Remove the middle node by linking the previous node to slow.next.
        prev.next = slow.next
        
        return head
← Back to All Questions