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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Delete the Middle Node of a Linked List

Difficulty: Medium

Problem Description

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.

Key Insights

  • The middle node is determined based on the size of the linked list.
  • For lists with an odd number of nodes, the middle is the exact middle node.
  • For lists with an even number of nodes, the middle is the first of the two middle nodes.
  • A two-pass approach can be used to find the middle node and remove it efficiently.

Space and Time Complexity

Time Complexity: O(n) - where n is the number of nodes in the linked list, since we may need to traverse the list twice. Space Complexity: O(1) - as we are using a constant amount of space.

Solution

To solve this problem, we can use a two-pointer approach. First, we traverse the linked list to determine its length. Then, we calculate the index of the middle node. Finally, we traverse the list again to remove the identified middle node by adjusting the pointers accordingly.

Code Solutions

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def deleteMiddle(head: ListNode) -> ListNode:
    if not head or not head.next:
        return None  # If there's only one node, return None.
    
    # Step 1: Calculate the length of the linked list
    length = 0
    current = head
    while current:
        length += 1
        current = current.next
    
    # Step 2: Find the index of the middle node
    middle_index = length // 2
    
    # Step 3: Remove the middle node
    current = head
    for _ in range(middle_index - 1):
        current = current.next
    
    current.next = current.next.next  # Bypass the middle node
    
    return head
← Back to All Questions