Comment on page

# 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.

EXAMPLE

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++;

}

count = 0;

}

prev->next = slow->next;

delete slow;

}

Last modified 4yr ago