2095. Delete the Middle Node of a Linked List

Description of the Problem

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, 10^5].
• 1 <= Node.val <= 10^5

Solution

Tags: Fast-Slow Pointer

Explanation

It is almost the same as 876. Middle of the Linked List except we want both pointers move to left by 1 for deletion at the end of the loop.

To acheive this, we have to make sure that there is at least 3 nodes after the faster pointer before an iteration of loop. Hence, at the termination of the loop, the number of node must less than 3. The slow pointer always point to the previous node of the middle node.

Code (Java)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode deleteMiddle(ListNode head){
        if (head == null || head.next == null)
            return null;
        
        ListNode slow = head;
        ListNode fast = head;

        while (fast.next != null && fast.next.next != null && fast.next.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }

        slow.next = slow.next.next;

        return head;
    }
}

Code (C++)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {

public:
    ListNode* deleteMiddle(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return nullptr;
        
        ListNode * slow = head;
        ListNode * fast = head;

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

        slow->next = slow->next->next;

        return head;
    }
};

Complexity

Time complexity:

• \(T(n) = O(n/2)\)

Auxiliary Space:

• \(S(n) = O(1)\)