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