Log In
26 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$;
in DS
edited by

2 Answers

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

edited by
11 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.

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.


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.

Related questions

53 votes
10 answers
A hash table of length $10$ uses open addressing with hash function $h(k) = k \: mod \: 10$, and linear probing. After inserting $6$ ... insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above? $10$ $20$ $30$ $40$
asked Apr 21, 2016 in DS jothee 9.3k views
20 votes
3 answers
A hash table of length $10$ uses open addressing with hash function $h(k) = k \mod 10$, and linear probing. After inserting $6$ ... $46, 42, 34, 52, 23, 33$ $34, 42, 23, 52, 33, 46$ $46, 34, 42, 23, 52, 33$ $42, 46, 33, 23, 34, 52$
asked Sep 30, 2014 in DS jothee 2.6k views
35 votes
11 answers
In a binary tree with $n$ nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child? $0$ $1$ $\frac{(n-1)}{2}$ $n-1$
asked Sep 29, 2014 in DS jothee 5.4k views
31 votes
7 answers
A circularly linked list is used to represent a Queue. A single variable $p$ is used to access the Queue. To which node should $p$ point such that both the operations $\text{enQueue}$ and $\text{deQueue}$ can be performed in constant time? rear node front node not possible with a single pointer node next to front
asked Sep 19, 2014 in DS Kathleen 9.3k views