The Gateway to Computer Science Excellence
+4 votes

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

node* reverse(node* trav){
            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:

  1. reverse(trav->next) -> next = trav;
  2. trav->next -> next = trav;
  3. trav -> next = trav;
  4. trav = reverse(trav->next);
in Programming by Veteran (431k points)
edited by | 455 views
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.

1 Answer

+3 votes
Recursive Function to reverse linked list :

node* reverse(node* trav){
        reverse(trav->next) = trav;
        else head = trav;
        return trav;
by Veteran (60.9k points)
I think none of the options given in the question matches.

In the test the correct option is given as (1)

Consider Linked List 1->2->3->NULL. Suppose trav is pointing to node 1

Option A: reverse(trav->next) -> next = trav;  

reverse(trav->next) will reverse the remaining list and returns it head.

that is it will return the head of the list 3->2->NULL. Now if we do reverse(trav->next)->next = trav then  we will get the following result.


Correct me if my understanding is wrong.


reverse_list(node * trav)


   if(!trav->next) return trav; // only one node



       node * next_node = trav->next; // get pointer to the next node

        node * rest = reverse_list(next_node); // reverse rest of the list

        next_node - > next = trav; // attach cur node to end of reversed list

        return rest; // return head of reversed list




Please correct me if my understanding is wrong
In the question it is mentioned that the function returns the head in a global variable- not as a return value.
Does this mean that the function returns the tail of the reversed list??
yes, it is.
Please correct the question . change "where the head of the reversed list is supposed to be returned' to "where the tail of the reversed list is supposed to be returned". This line is causing confusion.
where is NULL set as next of the last node??
yes the tail is getting returned and question need to be changed. Since the tail is getting returned, finally we can set its next as NULL. right??

@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

Related questions

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
50,737 questions
57,321 answers
105,145 users