Skip to content
GATETECH
Official PYQ · 2010Q36Linked ListsMCQ1 mark

GATE CS 2010 Q36 — Linked Lists

Explain with AI

The following C function takes a singly-linked list as input argument. It modifies the list by moving the last element to the front of the list and returns the modified list. Some part of the code is left blank.

typedef struct node 
{
    int value;
    struct node *next;
} Node;    
Node *move_to-front(Node *head) 
{
    Node *p, *q;
    if ((head == NULL) || (head -> next == NULL))
        return head;
    q = NULL; 
    p = head;
    while (p->next != NULL)
    {
        q=p;
        p=p->next;
    }
    _______________ 
    
    return head;  
    
}

Choose the correct alternative to replace the blank line.

Choose one option
View worked solution

Answer: D

To move the last node of a singly-linked list to the front, we first need to identify the last node and the second-to-last node. Let's trace the state of the pointers after the while loop terminates:

  • The loop condition is p->next != NULL. When the loop terminates, p points to the last node of the list.
  • Since q tracks the node just behind p (via q = p), q points to the second-to-last node of the list.

To move the last node (p) to the front of the list, we must perform the following three logical steps in order:

  1. Disconnect the last node: The second-to-last node q must now become the new end of the list, so its next pointer must be set to NULL: 
    q->next = NULL;
  2. Link the last node to the old head: The node p (which is being moved to the front) must point to the current first node of the list (head): 
    p->next = head;
  3. Update the head pointer: The head pointer must now point to the new first node p: 
    head = p;

Combining these steps, the correct sequence of statements is:

q→next = NULL; p→next = head; head = p;\text{q} \rightarrow \text{next = NULL; p} \rightarrow \text{next = head; head = p;}

This matches Option D.

Why other options are incorrect:

  • Option A: Setting q = NULL loses the reference to the second-to-last node, leaving its next pointer still pointing to p, which creates a cycle.
  • Option B: Executing head = p; before p->next = head; makes p->next point to p itself, creating a self-loop.
  • Option C: Setting p->next = q; points the new head back to the second-to-last node, which incorrectly reverses the end of the list and loses the rest of the list.

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

Published
Report a correction
Keep exploringMore Linked Lists questions