Linked List Reversal

Reverse a Linked List.

Node *ReverseLinkedListIterative(Node *n)
{
    Node *priv = nullptr;
    Node *temp = nullptr;
 
    while (nullptr != n)
    {
        temp = n->next;
        n->next = priv;
        priv = n;
        n = temp;
    }
 
    return priv;
}
 
// Input: head->n->n->n->nullptr
// We will solve recursively as follows:
// nullptr<-head<-[ReverseLinkedListRecursive(head->next)]
Node *ReverseLinkedListRecursive(Node *n)
{
    if (nullptr == n || nullptr == n->next)
        return n;
    // Note that before we cut off the rest of the list from the head and send
    // it to this function recursively n->next which is now the head of the rest
    // of the list, will become the tail after the function returns, so we record it now
    Node *rest_tail = n->next;
    Node *rest_head = ReverseLinkedListRecursive(n->next);
    // Now we have a head and a tail for the rest of the list so n, which is the old head
    // is now the tail and will point to nullptr and rest's tail will point to it
    n->next = nullptr;
    rest_tail->next = n;
 
    return rest_head;
}