Delete Middle Node

2.3 Delete Middle Node: 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.

Input: the node c from the linked list a - >b- >c - >d - >e- >f
Result: nothing is returned, but the new linked list looks like a - >b- >d - >e->f
  • Main idea is to use a slow and faster iterator. Moving the faster iterator 2x as fast as the slow means once the fast reaches the end, the slow one will be half way through.

  • Then, keeping track of the previous node, we just shift pointers around, and delete the midpoint!

Node *del_midpoint(Node *head) {
    Node *slow, *fast, *prev;
    slow = fast = head;
    prev = nullptr;
    if (!head) return slow;

    int count = 0;
    while (fast) {
        prev = slow;
        slow = slow->next;
        while (count < 2 && fast) {
            fast = fast->next;
        count = 0;
    prev->next = slow->next;
    delete slow;

Last updated