The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+18 votes

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)
    return head;  

Choose the correct alternative to replace the blank line.

  1. $q=NULL; p \rightarrow next = head; head = p$;
  2. $q \rightarrow next = NULL; head = p; p \rightarrow next = head$;
  3. $head = p; p \rightarrow next =q; q \rightarrow next = NULL$;
  4. $q \rightarrow next = NULL; p \rightarrow next = head; head = p$;
asked in DS by Veteran (101k points)
edited by | 1.8k views

2 Answers

+26 votes
Best answer

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).

answered by Boss (11.5k points)
edited by
+7 votes

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.

answered by Boss (30.8k points)
But when we set q->next=NULL, it will cause the node at p to be set to NULL thus losing the value field.
where is the picture ??

 p→next=head; and after that head=p; will link last node to first node.

but, q->next=NULL; will not cause any effect whether it is written at first or at middle or at last, it makes q's linked node as last node.


Why not option b?

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

39,512 questions
46,664 answers
57,481 users