# GO2017-Programming-1-30

590 views

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

node* reverse(node* trav){
if(trav->next)
__________________
else
{
}
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);

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

Recursive Function to reverse linked list :

node* reverse(node* trav){
if(trav->next)
reverse(trav->next) = 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

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

## Related questions

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
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)$