GATE Overflow | Programming | Test 1 | Question: 30

Question

Consider the following incomplete C function for reversing a singly linked list.

node* reverse(node* trav){
        if(trav->next)
                __________________
        else 
        {
            head -> next = null;
            head = trav;
        }
        return trav;
}

Here, head is a global pointer pointing to the head of the list and where the head of the reversed list is supposed to be returned. The missing line can be correctly filled by:

• A. reverse(trav->next) -> next = trav;
• B. trav->next -> next = trav;
• C. trav -> next = trav;
• D. trav = reverse(trav->next);

Comments

Options B and C can't be possible, clearly. They're don't even traverse the whole list, how would they reverse it.

Now make a dummy list and try Options A and D. A wins.

Answer 1

Recursive Function to reverse linked list :

node* reverse(node* trav){
        if(trav->next)
        reverse(trav->next) = trav;
        else head = trav;
        return trav;
}

Comments

@arjun SIr please confirm ??

After reverse : Last node next ptr should be set to null, somehow right ? 

Either it has be managed inside this code or some other way. correct ?

---

yes, you are correct. I corrected it now, else the last node is not pointing to NULL.

---

where is code for backtracking