Past exam question: 2074 Bhadra (Regular), Q5
Open in the Padhaiko appQuestion
How do you delete a node at the end of the doubly linked list? Explain how the addition of polynomial equations is done using linked list.
Solution
Deleting the Last Node of a Doubly Linked List:
- Empty List (
head == NULL): Underflow; returnNULL. - Single Node (
head->next == NULL):free(head), returnNULL. - Multiple Nodes: Traverse
temp = headuntiltemp->next == NULL(or usetail). Then settemp->prev->next = NULLandfree(temp).
DNode *deleteEnd(DNode *head) {
if (head == NULL) return NULL;
if (head->next == NULL) {
free(head);
return NULL;
}
DNode *temp = head;
while (temp->next != NULL) temp = temp->next;
temp->prev->next = NULL;
free(temp);
return head;
}Polynomial Addition Using Linked List: Each non-zero term is stored in a node (coeff, exp, next) sorted in descending order of exp. Using two pointers p1 and p2:
- While both
p1andp2are non-null:- If
p1->exp > p2->exp: append(p1->coeff, p1->exp)to result, advancep1. - Else if
p1->exp < p2->exp: append(p2->coeff, p2->exp)to result, advancep2. - Else (
p1->exp == p2->exp): computesum = p1->coeff + p2->coeff; ifsum != 0, append(sum, p1->exp); advance bothp1andp2.
- If
- Append all remaining nodes of whichever list (
p1orp2) is non-empty.
Example: (the and cancel).
Answer:
- Delete End of Doubly Linked List: Traverse to last node
temp, settemp->prev->next = NULL, and freetemp(handling empty and single-node lists). - Polynomial Addition: Merge two exponent-sorted linked lists in time, copying unmatched exponents and summing coefficients when exponents match.