Chapter 2 - Problem 3 - Delete Middle Node

Problem

Implement an algorithm to delete a node in the middle (i.e., any node but the first and last node, not necessarily the exact middle) of a singly linked list, given only access to that node.

EXAMPLE
Input: the node c from the linked list a->b->c->d->e->f
Output: nothing is returned, but the new linked list looks like a->b->d->e->f

Solution

Graphic explanation:

Solution in C++

template<typename T>
class Node {
    public:
        T data;
        Node* next;
        
        Node() = default;
        Node(const T& value) : data(value), next(NULL) {}
};

template<typename T>
class LinkedList {
    protected:
        Node<T>* head;
};

template<typename T>
class Solution : public LinkedList<T> {
    public:
        void deleteMiddleNode(Node<T>* node) {
	        /* We don't want the first node and last node */
            if(node == NULL || node->next == NULL)
                return;
            Node<T>* temp = node->next;
            node->data = node->next->data;
            node->next = node->next->next;
            delete temp;
        }
};