Reverse List

Reverse a singly linked list.

Iterative solution

Iterate through the linked list. In the loop, change next to prev, prev to current and current to next.

Node * LinkedList::reverse(Node *head) {
    Node *prev = NULL;
    Node *cur = head;
    Node *next = head->next;
    while (cur) {
        next = cur->next;
        cur->next = prev;
        prev = cur;
        cur = next;
    }
    return prev;
}

Recursive solution

Divide the linked list into two part, the head node and the rest. Reverse the rest linked list and return the new head node. The tricky part is to link the current head to the revered list. We can access the tail node by head->next, then link the head to the tail node. Remember to set the current head's next pointer to null.

Node * LinkedList::reverse(Node *head) {
    if (!head || !head->next) return head;

    Node *rest = reverse(head->next);
    head->next->next = head;
    head->next = NULL;

    return rest;
}