GATE 2025 CS (CS1) – Question 62
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 below (code for creating L1 and L2 is not provided here). L1 contains 9 nodes, and L2 contains 7 nodes.
L1: 1 -> 7 -> 12 -> 3 -> 9 -> 5 -> 11 -> 15 -> 8
L2: 1 -> 11 -> 6 -> 9 -> 15 -> 12 -> 4
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){
query = ptr1->next->data;
if (find (query, L2))
ptr1->next = ptr1->next->next;
else ptr1 = ptr1->next;
}
...
return 0;
}
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 5
Explanation
The loop starts with `ptr1=L1` (the head, value 1) and looks at `ptr1->next`. If its value is found in `L2`, the node is unlinked; otherwise `ptr1` moves forward. The head itself is never tested.
$L1$: 1 → 7 → 12 → 3 → 9 → 5 → 11 → 15 → 8. $L2$ contains $\{1,11,6,9,15,12,4\}$.
Check nodes after the head:
- 7: not in L2, keep.
- 12: in L2, **removed**.
- 3: keep.
- 9: in L2, **removed**.
- 5: keep.
- 11: in L2, **removed**.
- 15: in L2, **removed**.
- 8: keep.
Remaining list: 1 → 7 → 3 → 5 → 8, which has $9-4=\mathbf{5}$ nodes.