Skip to content
GATETECH
Official PYQ · 2025Set 1 · Q52Linked ListsNAT2 marks

GATE CS 2025 Set 1 Q52 — Linked Lists

Explain with AI

Let LIST\mathrm{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, L1L1 and L2L2, whose contents are given in the figure below (code for creating L1L1 and L2L2 is not provided here). L1L1 contains 99 nodes, and L2L2 contains 77 nodes.

Consider the following C program segment that modifies the list L1L1. The number of nodes that will be there in L1L1 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;
}
View worked solution

Answer: 5:5

Based on the figures provided in the exam:

  • L1L1 contains 99 nodes: 1→2→3→4→5→6→7→8→91 \to 2 \to 3 \to 4 \to 5 \to 6 \to 7 \to 8 \to 9
  • L2L2 contains 77 nodes: 2→4→6→8→10→12→142 \to 4 \to 6 \to 8 \to 10 \to 12 \to 14

The function find(query, L2) returns 1 if the query value exists in L2L2, and 0 otherwise.

In the main function, the loop traverses L1L1 using ptr1 starting at the head (L1L1):

  • The loop condition is ptr1->next != NULL, and it checks query = ptr1->next->data. This means the first node of L1L1 (value 11) is never checked or deleted.
  • For any subsequent node, if its data is present in L2L2, it is bypassed (deleted) via ptr1->next = ptr1->next->next.
  • If the data is not in L2L2, ptr1 simply advances to the next node.

Tracing the deletion process for each node in L1L1:

  • Node 1: Head node, skipped (kept).
  • Node 2: Present in L2  ⟹  L2 \implies deleted.
  • Node 3: Not in L2  ⟹  L2 \implies kept.
  • Node 4: Present in L2  ⟹  L2 \implies deleted.
  • Node 5: Not in L2  ⟹  L2 \implies kept.
  • Node 6: Present in L2  ⟹  L2 \implies deleted.
  • Node 7: Not in L2  ⟹  L2 \implies kept.
  • Node 8: Present in L2  ⟹  L2 \implies deleted.
  • Node 9: Not in L2  ⟹  L2 \implies kept.

After execution, the remaining nodes in L1L1 are 1→3→5→7→91 \to 3 \to 5 \to 7 \to 9. Thus, the number of nodes in L1L1 is 5.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Linked Lists questions