Consider the following C code fragment that removes duplicates from an ordered…
1997
Consider the following C code fragment that removes duplicates from an ordered singly linked list of integers.
typedef struct Node {
int val;
struct Node *next;
} Node;
Node *remove_duplicates(Node *head, int *j) {
Node *t1, *t2;
*j = 0;
t1 = head;
if (t1 != NULL)
t2 = t1->next;
else
return head;
*j = 1;
if (t2 == NULL)
return head;
while (t2 != NULL) {
if (t1->val != t2->val) { // S1
// S2 starts
(*j)++;
t1->next = t2;
t1 = t2;
// S2 ends
}
t2 = t2->next;
}
t1->next = NULL;
return head;
}
Assume the list contains n elements (n >= 2).
(a) How many times is the comparison in S1 made?
(b) What are the minimum and maximum numbers of times the S2 block executes?
(c) What does the value stored in *j represent when the function completes?
- A.
(a) n - 1 times; (b) minimum 0 and maximum n - 1 times; (c) *j stores the number of distinct nodes in the list.
- B.
(a) n times; (b) minimum 0 and maximum n - 1 times; (c) *j stores the number of distinct nodes in the list.
- C.
(a) n - 1 times; (b) minimum 1 and maximum n - 1 times; (c) *j stores the number of distinct nodes in the list.
- D.
None of the above
Attempted by 31 students.
Show answer & explanation
Correct answer: A
The pointer t1 initially refers to the first node and t2 starts from the second node. In every iteration of the while loop, t2 advances to the next node, so the comparison in S1 is made once for each of the remaining n - 1 nodes.
The S2 block executes only when t2 contains a value different from the current distinct tail node t1. If all values in the ordered list are identical, S2 never executes, so the minimum is 0. If all values are distinct, every node after the first is linked as a new distinct node, so S2 executes n - 1 times.
For a nonempty list, *j is set to 1 and then incremented exactly when another distinct node is found. Therefore, when the function completes, *j stores the number of distinct nodes in the list.