Reverse a singly linked list

This is a very classic interview question. It demonstrates the ability to work with basic data structure and pointers. The seemingly easy question has some pitfalls. Nearly every candidate starts with two temporary pointers and eventually finds out that you need three. You need to point to the current node (the one you’re handling), the previous node (so you can point back to it), and the next node (so you can prevent lost of the next node). Also, you should not forget to make the first node point to NULL.

There are two solutions to this question. One is iterative and the other is recursive. 

Node* reverse_iterative(Node* head) {
    Node* prev = head;
    Node* curr = head->next;
    Node* next = head->next->next;
    prev->next = NULL;

    while(curr->next) {
        curr->next = prev;
        prev = curr;
        curr = next;
        next = next->next;
    }
    curr->next = prev;
    return curr;
}

The recursive version is shown as follow:

Node* reverse(Node* prev, Node* curr) {
    // If reached the end of the list, return the head
    if(curr->next == NULL) {
        curr->next = prev;
        return curr;
    }
    // Remember the next node
    Node* next = curr->next;
    // Change current pointer to previous node
    curr->next = prev;
    return reverse(curr, next);
}

Node *reverse_recursive(Node* curr)
{
    return reverse(NULL, curr);
}

Although recursive version is more straightforward, in general we prefer the iterative version because if the list is very large, this version would fail because of stack overflow.

Note that there are some variations of this question like "How to print a singly linked list in reverse order". In this case, if we are allowed to alter the data structure, we can reverse linked list first and print it from the beginning.