Microsoft Interview Question
Software Engineer / DevelopersOnother approach is to use stack.
1: Travel thru the list from the begining to the end and push each data in stack.
2: Just pop up the data from the stack and print them.
You can reverse a linked list in O(n) time with O(1) temp memory. (3 variables, i believe)
The major trick in this problem was just the recognition that, while the linked list must stay intact before and after the operation, it doesn't need to stay intact during the operation. You can reverse it, print it, then reverse it back.
Node* ReverseList( Node ** List )
{
Node *temp1 = *List;
Node * temp2 = NULL;
Node * temp3 = NULL;
while ( temp1 )
{
*List = temp1; //set the head to last node
temp2= temp1->pNext; // save the next ptr in temp2
temp1->pNext = temp3; // change next to privous
temp3 = temp1;
temp1 = temp2;
}
return *List;
}
One approach is to reverse the linked list which takes O(n) and print the list which takes another O(n). In total O(2*n) which is nothing but O(n).
- srihari January 04, 2006But for reversing we need two variables to hold the address of the nodes while reversing. If we approximate the use of the two variables as O(1)memory, this approach sounds plausible.
Please discuss other approaches if any.