GATE CSE 2010 | Question: 36

Question

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.

• A. $q=NULL; p \rightarrow next = head; head = p$;
• B. $q \rightarrow next = NULL; head = p; p \rightarrow next = head$;
• C. $head = p; p \rightarrow next =q; q \rightarrow next = NULL$;
• D. $q \rightarrow next = NULL; p \rightarrow next = head; head = p$;

Comments

There is a typo in question.

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

typedef identifier should be Node not node.

Ref: https://www.iitr.ac.in/gate/papers/GATE2010/GATE2010_CS.pdf?download_file=papers/GATE2010/GATE2010_AE.pdf

Answer 1

As per given code $p$ points to last node which should be head in modified.

$q$ is the previous node of tail which should be tail for modified

Answer is (D).

Answer 2

after the last iteration of the while loop, here's how the condition look like :

on selecting option D; we serve the purpose of moving the last node to the front of the linked list. this is how it works:

its first statement makes $q$ the last node
second statement makes the last node $p$ points to the first node
last statement declares $p$ as the $head$ of the linked list.

Comments

Answer b will be wrong because head =p will make element pointed by p as head then p-> next = head will reset head to it's original position??

Can someone confirm if my understanding is correct?

---

Your reasoning is right .lets confirm ii by taking a example.let linked list contain 5 node numbered 0,1,2,3,4 at the end the while loop p->next =null and p will will be pointed to 4 and q will have address of 3 . So for option b q->next =null means we are breaking the link between 3 and 4;

next we are assigning p to head which means now we have address of node 4 in head in next statement p->next=head; assigning same address to its next which does not add node 4 to front of the list.

---

What about option c ,i think it should also correct