search
Log In
4 votes
590 views

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
590 views
0
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){
        if(trav->next)
        reverse(trav->next) = trav;
        else head = trav;
        return trav;
}
0
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
In the question it is mentioned that the function returns the head in a global variable- not as a return value.
1
Does this mean that the function returns the tail of the reversed list??
1
yes, it is.
0
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
where is NULL set as next of the last node??
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??
2

@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
yes, you are correct. I corrected it now, else the last node is not pointing to NULL.
0
where is code for backtracking
Answer:

Related questions

2 votes
2 answers
1
488 views
What will be the output of the following code? #include <stdio.h> #include <string.h> int main() { struct mystruct{ char *name; unsigned int age; }; struct mystruct st1 = {"Ram", 12}; printf("%lu %u", strlen(st1.name), st1.age); } 4 12 3 12 compile error run time error
asked Oct 19, 2016 in Programming Arjun 488 views
7 votes
2 answers
2
625 views
int foo(int n) { if(n > 10000) return 1; int sum = 0, i; for( i = 0; i < n; i++) { sum += i; } return sum; } The value returned by the above function is $\Theta\left(n^2\right)$ $\Theta\left(n\right)$ $\Theta\left(1\right)$ $\Omega\left(n^2\right)$
asked Oct 19, 2016 in Programming Arjun 625 views
0 votes
3 answers
3
624 views
Which of the following statements is true regarding C language? S1: C is a functional language S2: C is a declarative language S3: C is a procedural language S4: C is a structured language S1, S2 and S3 only S3 and S4 only S2, S3 and S4 only S1, S3 and S4 only
asked Oct 19, 2016 in Programming Arjun 624 views
2 votes
4 answers
4
294 views
What will be the output of the following code? #include <stdio.h> int main() { char a = 'A', z = 'Z'; printf("%d", z-a); }
asked Oct 19, 2016 in Programming Arjun 294 views
...