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 224 students.

Sign up free to check your answer

Sign up free

Explore the full course: Gate Guidance By Sanchit Sir

Loading lesson…