Past exam question: 2062 Baishakh (Regular / Back), Q1
Open in the Padhaiko appQuestion
Write an algorithm to delete a node before a node in singly and doubly linked list.
Solution
1. Delete Node Before a Given Target (targetKey) in Singly Linked List:
Algorithm SLL_DELETE_BEFORE(head, targetKey):
1. If head == NULL or head->next == NULL or head->data == targetKey:
Print "No node exists before target"; Return head
2. If head->next->data == targetKey: // target is 2nd node -> delete head
temp = head; head = head->next
Free(temp); Return head
3. prev2 = head, prev1 = head->next, curr = prev1->next
4. While curr != NULL and curr->data != targetKey:
prev2 = prev1; prev1 = curr; curr = curr->next
5. If curr == NULL:
Print "Target not found"; Return head
6. prev2->next = curr
7. Free(prev1)
8. Return head2. Delete Node Before a Given Target (targetKey) in Doubly Linked List:
Algorithm DLL_DELETE_BEFORE(head, targetKey):
1. curr = head
2. While curr != NULL and curr->data != targetKey:
curr = curr->next
3. If curr == NULL or curr->prev == NULL:
Print "No node exists before target"; Return head
4. del = curr->prev
5. If del == head: // node to delete is head
head = curr
curr->prev = NULL
Else:
del->prev->next = curr
curr->prev = del->prev
6. Free(del)
7. Return headAnswer:
In a singly linked list, deleting the node before targetKey tracks two trailing pointers (prev2, prev1) and splices prev2->next = curr; in a doubly linked list, curr->prev directly identifies del so del->prev->next = curr and curr->prev = del->prev (updating head if del == head).