Bloomberg LP Interview Question
Software Engineer / DevelopersHere is what I came up with on a first try
NODE* ReverseLinkedList(NODE* node)
{
if( !node )
return NULL;
NODE* p;
if( node->next )
p = ReverseLinkedList(node->next);
else
{
/* I am the last node - I will be the head now */
return node;
}
node->next = NULL;
NODE* temp = p->next;
if( !temp )
{
p->next = node;
}
else
{
while( temp->next )
temp = temp->next;
temp->next = node;
}
return p;
}
http://www.trap17.com/index.php/Data-Structures-Linked-List-Reverse_t52777.html
Best one:
Linked_list_t* reverse_with_recursion_anotherway(linked_list_t* current, linked_list_t* parent)
{
linked_list_t* revhead = NULL;
if(current == NULL)
revhead = parent;
else
{
revhead = reverse_with_recursion_anotherway(current->next, current);
current->next = parent;
}
return revhead;
}
- mg August 08, 2009