Delete the Middle Node of a Linked List

class Solution {
public:
    ListNode* removeMiddleNode(ListNode* start) {
        if (start -> next == nullptr)
            return nullptr;
            
        ListNode *slowPointer = start, *fastPointer = start -> next -> next;
            
        while (fastPointer != nullptr && fastPointer -> next != nullptr) {
            slowPointer = slowPointer -> next;
            fastPointer = fastPointer -> next -> next;
        }
            
        slowPointer -> next = slowPointer -> next -> next;
        return start;
    }
};

This summary guides you through a C++ implementation designed to delete the middle node from a singly linked list. The goal is to return the modified linked list with one less node, specifically without the middle node.

• The solution employs the two-pointer technique using a slowPointer and a fastPointer.
• Begin by checking if the linked list is extremely short. If the start node's next points to nullptr, there's only one element, or the list is empty, in which case return nullptr.
• Initialize slowPointer at the start node and fastPointer several steps ahead — specifically, at the second node's next if it exists. This sets up for the traversal where fastPointer will move twice as fast as slowPointer.
• Traverse through the linked list:
  • Move slowPointer one step at a time.
  • Move fastPointer two steps at a time.
• Continue this until fastPointer is either at the end of the list or has no further nodes (nullptr) to jump to.
• Adjust the next pointer of the slowPointer to skip its next node (effectively removing the middle node since slowPointer would be just before the middle when fastPointer reaches the end).
• Return the modified start of the linked list as the final result.

This method efficiently locates and removes the middle node in O(n) time with O(1) space complexity, utilizing a classic fast and slow pointer strategy.

class Solution {
    public ListNode removeMiddleNode(ListNode start) {
        if (start.next == null)
            return null;
            
        ListNode slow = start, fast = start.next.next;
            
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
            
        slow.next = slow.next.next;
        return start;
    }
}

The solution provided addresses the problem of deleting the middle node from a linked list using Java. The approach implemented in the solution utilizes the two-pointer technique, consisting of "slow" and "fast" pointers, to determine the middle of the list efficiently.

Here's a breakdown of how the solution operates:

1. Check if the start.next is null, indicating the list only contains one node. If true, return null as the list will be empty after removing the middle.

2. Initialize two pointers, slow starting at the head of the list and fast starting at the second node's next node (two steps ahead).

3. Iterate through the list while fast and fast.next are not null. Move slow one step for each two steps fast takes. When fast reaches the end of the list, slow will be exactly before the middle node of the linked list.

4. Remove the middle element by setting slow.next to slow.next.next, effectively skipping over the middle node.

5. Return the modified linked list starting from start.

This method ensures that the middle node is successfully removed while maintaining the integrity of the linked list, and it works efficiently with a time complexity of O(n), where n is the number of nodes in the list.

var removeMiddleNode = function(headNode) {
    if (headNode.next == null)
        return null;
        
    let slowPointer = headNode, fastPointer = headNode.next.next;
        
    while (fastPointer != null && fastPointer.next != null) {
        slowPointer = slowPointer.next;
        fastPointer = fastPointer.next.next;
    }
        
    slowPointer.next = slowPointer.next.next;
    return headNode;
};

The provided JavaScript function, removeMiddleNode, targets deleting the middle node from a singly linked list. Here's a breakdown of how the function operates:

• Initially, it checks if the headNode has no following nodes by checking headNode.next. If this node is null, the function returns null, indicating the list was already empty or had only one element.
• Two pointers, slowPointer and fastPointer, are used for traversal of the linked list. slowPointer progresses one node at a time, while fastPointer moves two nodes at a time. This difference allows slowPointer to reach the middle of the list when fastPointer reaches its end.
• A loop continues until fastPointer either becomes null or has no next node, ensuring traversal to the end of the list. During each iteration, slowPointer and fastPointer are advanced accordingly.
• Once the loop concludes, slowPointer directly links to the node after its next node (slowPointer.next = slowPointer.next.next), effectively skipping the middle node and removing it from the list.
• Finally, the modified list with the middle node removed is returned by handing back the headNode.

This solution accomplishes the middle node removal efficiently by using the two-pointer technique to avoid counting or recalculating the list's length.