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 updated
Was this helpful?