Reverse a Singly Linked List

Recursive Solution:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
                
        ListNode* newHead =NULL; 

       if( head )
        reverse(head,newHead);
        
        return newHead;
    }

    void reverse(ListNode* head, ListNode*& newHead){
        
        if( head->next == NULL ){
            newHead = head;
        }else{
            reverse(head->next,newHead); 

            // equivalent to head->next->next = head->next;

            ListNode* tmp = head->next; 
            tmp->next = head; // point next of the node to previous node
            head->next = NULL;
        }
        
    }
};