2095. Delete the Middle Node of a Linked List

• Link: https://leetcode.com/problems/delete-the-middle-node-of-a-linked-list/

Question

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

Approach 1: Brute Force

Intuition

• Calculate the Size first

Algorithm

0. Edge case: if (head == NULL || head->next == NULL) return NULL
1. Declare & initialize int size = 0
2. Declare & initialize ListNode* curr = head
3. Loop through the LL using curr
   1. Increment the size by 1
4. Declare & initialize int middle = size / 2
5. Reinitialize curr = head
6. Loop through the LL till i < middle
7. Declare & initialize ListNode* toDel = curr->next
8. curr->next = curr->next->next
9. Delete the toDel node
10. Return `head

Code

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return NULL;
        }

        int size = 0;
        ListNode* curr = head;

        while (curr) {
            size++;
            curr = curr->next;
        }

        int middle = size / 2;
        curr = head;

        for (int i = 0 ; i < middle-1 ; i++) {
            curr = curr->next;
        } 

        ListNode* toDel = curr->next;

        curr->next = curr->next->next;

        delete toDel;
        
        return head;

    }
};

Complexity Analysis

• Time Complexity: $O(n+\frac{n}{2})=O(n)$
• Space Complexity: $O(1)$

Approach 2: Optimal

Intuition

• Fast & slow pointer

Algorithm

0. Edge case: if (head == NULL || head->next == NULL) return NULL
1. Declare & initialize ListNode* fast = head & ListNode* slow = head.
2. Increment fast by 2 nodes to create the offset so slow pointer reaches 1 node before the middle node.
3. Loop through the LL while fast & fast->next exists
   1. Increment slow by 1 node
   2. Increment fast by 2 nodes
4. slow->next = slow->next->next
5. Delete the middle node
6. return head.

Code

class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return NULL;
        }
        ListNode* fast = head;
        ListNode* slow = head;
        fast = fast->next->next;

        while (fast && fast->next ) {
            slow = slow->next;
            fast = fast->next->next;
        }

        slow->next = slow->next->next;
        return head;
    }
};

Complexity Analysis

• Time Complexity: $O\left(\frac{n}{2}\right)=O(n)$
• Space Complexity: $O(1)$