Reversing a Linked List

I heard this is one of the most frequently asked questions in an interview. It seems to be asked quite a lot in phone screens. May be because it's simple, gives a good idea whether you have grasp of pointers and whether you have an idea of basic data structure (Of course linked list). There are 2 ways to approach this problem. The first one is recursive. But you might not want to come up with recursive solution during interview unless interviewer explicitly directs you to do so. Why? Because recursion is slow and takes up lot of memory if linked list is long. The second solution is also obvious. You go through each node in the list and adjust the pointers. Before proceeding it might be wise to ask the interviewer whether it's an singly or doubly linked list. Here we assume it's a singly linked list. The code is given below.

Node* reverse_list(Node *head) {
if(head == NULL)
return;

Node *current = head, *temp, *new_list = 0;

while(current != 0) {
temp = current->next;
current->next = new_list;
new_list = current;
current = temp;
}

//return new head
return new_list;

}