Consider the following C code fragment that removes duplicates from an ordered…

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?

  1. A.
    • (a) n - 1 times; (b) minimum 0 and maximum n - 1 times; (c) *j stores the number of distinct nodes in the list.

  2. B.
    • (a) n times; (b) minimum 0 and maximum n - 1 times; (c) *j stores the number of distinct nodes in the list.

  3. C.
    • (a) n - 1 times; (b) minimum 1 and maximum n - 1 times; (c) *j stores the number of distinct nodes in the list.

  4. D.

    None of the above

Attempted by 208 students.

Show answer

Correct answer: A

The worked solution is available to enrolled students.

Explore the full course: Iocl Engineers Officers Grade A Paper 2

Loading lesson…