Linked List Deletion removes a node by making the previous node point directly to the deleted node's successor. Deleting the head is O(1). Deleting by value or position requires traversal to find the node and its predecessor. Memory should be freed after deletion in C++.
Node* deleteHead(Node* head) {
if (!head) return nullptr;
Node* temp = head;
head = head->next;
delete temp;
return head;
}
Node* deleteVal(Node* head, int val) {
if (!head) return nullptr;
if (head->val == val) return deleteHead(head);
Node* curr = head;
while (curr->next && curr->next->val != val) curr = curr->next;
if (curr->next) { Node* temp = curr->next; curr->next = temp->next; delete temp; }
return head;
}To delete a node, we find its predecessor and set predecessor.next = node.next. This bypasses the node, effectively removing it from the chain. We must also free memory in C++.
Deleting the head node is a special case since there is no predecessor. We simply return head.next as the new head. Always handle empty list and single-node list cases.
A clever trick: to delete a node when you only have a pointer to it (not its predecessor), copy the next node's value into the current node and delete the next node instead.
Quiz coming soon for this algorithm.