in Programming edited by
1,205 views
4 votes
4 votes

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:

  1. reverse(trav->next) -> next = trav;
  2. trav->next -> next = trav;
  3. trav -> next = trav;
  4. trav = reverse(trav->next);
in Programming edited by
by
1.2k views

1 comment

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

1 Answer

4 votes
4 votes
Recursive Function to reverse linked list :

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

10 Comments

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.

3->1

Correct me if my understanding is wrong.

 

reverse_list(node * trav)

{

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

   else

  {

       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
0
0
In the question it is mentioned that the function returns the head in a global variable- not as a return value.
0
0
Does this mean that the function returns the tail of the reversed list??
1
1
yes, it is.
1
1
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.
0
0
where is NULL set as next of the last node??
0
0
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??
0
0

@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 ?

2
2
yes, you are correct. I corrected it now, else the last node is not pointing to NULL.
2
2
where is code for backtracking
0
0
Answer:

Related questions