Skip to content
GATETECH
Official PYQ · 2008Q62Linked ListsMCQ1 mark

GATE CS 2008 Q62 — Linked Lists

Explain with AI

The following C function takes a single-linked list of integers as a parameter and rearranges the elements of the list. The function is called with the list containing the integers 1,2,3,4,5,6,71, 2, 3, 4, 5, 6, 7 in the given order. What will be the contents of the list after function completes execution?

struct node {
    int value;
    struct node *next;
};

void rearrange(struct node *list) {
    struct node *p, *q;
    int temp;
    if (!list || !list -> next) return;
    p = list; q = list -> next;
    while(q) {
        temp = p -> value; p->value =  q -> value;
        q->value = temp; p = q ->next;
        q = p? p ->next : 0;
    }   
}
Choose one option
View worked solution

Answer: B

To find the contents of the list after the execution of the rearrange function, let us trace the execution step-by-step.

The initial list is:
1→2→3→4→5→6→71 \to 2 \to 3 \to 4 \to 5 \to 6 \to 7

Before entering the loop, the pointers are initialized as:

  • p = list (points to the node with value 11)
  • q = list->next (points to the node with value 22)

Step-by-Step Execution:

  1. First Iteration (q is not NULL):
    • Swap the values of p and q: The values 11 and 22 are swapped.
    • The list becomes: 2→1→3→4→5→6→72 \to 1 \to 3 \to 4 \to 5 \to 6 \to 7
    • Update pointers:
      • p = q->next (points to the node with value 33)
      • q = p ? p->next : 0 (points to the node with value 44)
  2. Second Iteration (q is not NULL):
    • Swap the values of p and q: The values 33 and 44 are swapped.
    • The list becomes: 2→1→4→3→5→6→72 \to 1 \to 4 \to 3 \to 5 \to 6 \to 7
    • Update pointers:
      • p = q->next (points to the node with value 55)
      • q = p ? p->next : 0 (points to the node with value 66)
  3. Third Iteration (q is not NULL):
    • Swap the values of p and q: The values 55 and 66 are swapped.
    • The list becomes: 2→1→4→3→6→5→72 \to 1 \to 4 \to 3 \to 6 \to 5 \to 7
    • Update pointers:
      • p = q->next (points to the node with value 77)
      • q = p ? p->next : 0 (since p->next is NULL, q becomes NULL)

At the next check, the loop condition while(q) fails because q is NULL. The function terminates.

The final contents of the list are:
2,1,4,3,6,5,72, 1, 4, 3, 6, 5, 7

Therefore, the correct option is B.

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

Published
Report a correction
Keep exploringMore Linked Lists questions