Three 8ms solutions (1 iterative solution + 2 recursive solutions) in C++


  • 1
    G

    1> Iterative

        ListNode* reverseList(ListNode* head) 
        {
            ListNode* prev = NULL;
            
            while (head != NULL)
            {
                ListNode* next = head->next;
                head->next = prev;
                prev = head;
                head = next;
            }
            
            return prev;
        }
    

    2> Recursive

    • Tail recursion (similar idea to the iterative solution)
    ListNode* reverseList(ListNode* head) 
    {
        return helper(NULL, head);
    }
    
    ListNode* helper(ListNode* first, ListNode* second)
    {
        if (second == NULL)
        {
            return first;
        }
        
        ListNode* next = second->next;
        
        second->next = first;
        
        return helper(second, next);
    }
    
    • Normal recursion
    ListNode* reverseList(ListNode* head) 
    {
        if (!head || !head->next)
        {
            return head;
        }
            
        ListNode* node = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
           
        return node;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.