Past exam question: 2077 Chaitra (Regular), Q9
Open in the Padhaiko appQuestion
Explain with example how node in a singly linked list can be deleted?
Solution
Cases for Deleting the -th Node (1-Based Position):
- Empty List (
head == NULL): Report underflow and return. - Delete First Node (
n == 1): Savetemp = head, advancehead = head->next, andfree(temp). - Delete Node at Position :
- Walk pointer
prevfromheadfor steps soprevpoints to node . - If
prev == NULLorprev->next == NULL, position exceeds list length. - Otherwise, let
target = prev->next, setprev->next = target->next, andfree(target).
- Walk pointer
Algorithm and Example Trace:
Node *deleteNth(Node *head, int n) {
if (head == NULL || n < 1) return head;
if (n == 1) {
Node *temp = head;
head = head->next;
free(temp);
return head;
}
Node *prev = head;
for (int i = 1; i < n - 1 && prev != NULL; i++)
prev = prev->next;
if (prev == NULL || prev->next == NULL) return head;
Node *target = prev->next;
prev->next = target->next;
free(target);
return head;
}
Example: Given 10 -> 20 -> 30 -> 40 -> NULL, delete the node (30):
prevadvances step from10to20.target = 20->next(30);20->next = 30->next(40);free(30).- Resulting list:
10 -> 20 -> 40 -> NULL.
Answer:
To delete the -th node, handle n == 1 by advancing head = head->next; for , advance prev to position , relink prev->next = prev->next->next, and free the detached node. Deleting the 3rd node from 10 -> 20 -> 30 -> 40 yields 10 -> 20 -> 40.