GATE2025_CS1_Q62

Let LIST be a datatype for an implementation of linked list defined as follows:

typedef struct list { int data; struct list *next; } LIST;

Suppose a program has created two linked lists, L1 and L2, whose contents are given in the figure below. L1 contains 9 nodes, and L2 contains 7 nodes.

Consider the following C program segment that modifies the list L1. The number of nodes that will be there in L1 after the execution of the code segment is _______. (Answer in integer)

int find (int query, LIST *list) { while (list != NULL) { if(list->data == query) return 1; list = list->next; } return 0; } int main () { ... ptr1=L1; ptr2=L2; while (ptr1->next != NULL) { int query = ptr1->next->data; if (find(query, L2)) { ptr1->next = ptr1->next->next; } else { ptr1 = ptr1->next; } } ... return 0; }

✅ Final Answer:

The correct answer is 5.

🔹 Short Answer:

The code iterates through L1 using ptr1 and checks if the *next* node's data exists in L2. If it does, the next node is deleted by bypassing it. If not, ptr1 advances. The data values from L1 that are also in L2 are {12, 9, 11, 15}. These four nodes get deleted from L1. L1 initially has 9 nodes, so after deleting 4 nodes, it is left with 9 - 4 = 5 nodes.

🔸 Long Answer:

Let's trace the execution of the C code step-by-step to understand how list `L1` is modified.

Code Logic Breakdown

• ptr1: A pointer that traverses list L1.
• while (ptr1->next != NULL): The loop runs as long as `ptr1` is not pointing to the last node. This is key, as the code always inspects the node *after* `ptr1`.
• query = ptr1->next->data;: We get the data from the node we are about to potentially delete.
• if (find(query, L2)): If the data exists in L2, we execute the `if` block.
• ptr1->next = ptr1->next->next;: This is the deletion step. We make the current node's `next` pointer skip over the next node, effectively removing it from the list. Crucially, `ptr1` does **not** advance in this case, because its new `next` node needs to be checked in the next iteration.
• else { ptr1 = ptr1->next; }: If the data is not in L2, the node is safe. We simply advance `ptr1` to the next node to continue the scan.

Execution Trace

Values in L2 for easy lookup: {1, 11, 6, 9, 15, 12, 4}

1. Initial: `ptr1` is at node `1`. `L1`: 1 → 7 → 12 → 3 → 9 → 5 → 11 → 15 → 8
2. Iteration 1:
   • `ptr1` is at `1`. `ptr1->next` is `7`. `query` is 7.
   • `find(7, L2)` returns false.
   • `else` block: `ptr1` advances to node `7`.
   • `L1` is unchanged.
3. Iteration 2:
   • `ptr1` is at `7`. `ptr1->next` is `12`. `query` is 12.
   • `find(12, L2)` returns true.
   • `if` block: node `12` is deleted. Node `7` now points to node `3`. `ptr1` stays at `7`.
   • `L1`: 1 → 7 → 3 → 9 → 5 → 11 → 15 → 8
4. Iteration 3:
   • `ptr1` is at `7`. `ptr1->next` is now `3`. `query` is 3.
   • `find(3, L2)` returns false.
   • `else` block: `ptr1` advances to node `3`.
5. Iteration 4:
   • `ptr1` is at `3`. `ptr1->next` is `9`. `query` is 9.
   • `find(9, L2)` returns true.
   • `if` block: node `9` is deleted. Node `3` now points to node `5`. `ptr1` stays at `3`.
   • `L1`: 1 → 7 → 3 → 5 → 11 → 15 → 8
6. Iteration 5:
   • `ptr1` is at `3`. `ptr1->next` is now `5`. `query` is 5.
   • `find(5, L2)` returns false.
   • `else` block: `ptr1` advances to node `5`.
7. Iteration 6:
   • `ptr1` is at `5`. `ptr1->next` is `11`. `query` is 11.
   • `find(11, L2)` returns true.
   • `if` block: node `11` is deleted. Node `5` now points to node `15`. `ptr1` stays at `5`.
   • `L1`: 1 → 7 → 3 → 5 → 15 → 8
8. Iteration 7:
   • `ptr1` is at `5`. `ptr1->next` is now `15`. `query` is 15.
   • `find(15, L2)` returns true.
   • `if` block: node `15` is deleted. Node `5` now points to node `8`. `ptr1` stays at `5`.
   • `L1`: 1 → 7 → 3 → 5 → 8
9. Iteration 8:
   • `ptr1` is at `5`. `ptr1->next` is now `8`. `query` is 8.
   • `find(8, L2)` returns false.
   • `else` block: `ptr1` advances to node `8`.
10. Loop Termination: Now `ptr1` is at node `8`. `ptr1->next` is `NULL`. The `while` loop condition is false and the process stops.

Final Result

The nodes deleted contained the values {12, 9, 11, 15}. That's 4 nodes removed.

Final Count = Initial Count - Deleted Count = 9 - 4 = 5.

The final state of list L1 is:

Bibliography:
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language. Prentice Hall.
- Cormen, T. H., et al. (2009). Introduction to Algorithms. MIT Press. (Chapter 10: Elementary Data Structures).

Ask your doubts in comment form our GURUJEE will reply ASAP, click notify me button so that you get notified on reply.