Recursive C++ solution 9ms with Detailed Explanation


  • 0
    Y

    This might not be the most efficient solution, but I approached it as solving subproblems of LinkedList of n size.

    Breakdown of the problem
    Case 1: n = 0, aka no ListNodes, return NULL
    Case 2: n = 1, aka 1 ListNode, return itself
    Case 3: n >= 2, aka more than 2 ListNodes,

    1. Need to reverse pointer direction between 2 ListNodes*
    2. Need to set the tail as the new head
    3. Need to set the head as the new tail

    class Solution {
    public:

    ListNode* reverseList(ListNode* head) {
        /* Case 1: If there's nothing */
        if (!head){
            return NULL;
        }
        /* Case 2: If there's only one ListNode in the LinkedList */
        if (!head->next){
            return head;
        }
        /* Case 3: Two or more ListNodes */
        
        /* This will stored our new head */
        ListNode* newHead; 
        
        /* Let's reverse the LinkedList */
        reverse(head, head->next, &newHead);
        
        /* the original head is now the tail, so we need to set its next pointer to NULL to indicate the end */
        head->next = NULL; 
        
        /* return the head of the reversed LinkedList */
        return newHead;
    }
    
    /* Helper function to reverse the LinkedList */
    void reverse(ListNode* current, ListNode* after, ListNode** newHead){
        /* Base Case */
        /* If we reach the end of the linked  list e.g. (tail -> NULL) , set the tail(current) as the new head */
        if (!after){
            /* Modify the pointer to point at the tail(current), which is the new head. */
            *newHead = current;
            return;
        }
        
        /* Let's recurse! */
        reverse(current->next, after->next, newHead);
        
        /* Reverse the direction of the next pointers, so if you had 1 -> 2, it will now be 1 <- 2 */
        after->next = current;
        
        /* The reason we do this after the recursion call is because we want to reverse the pointers ONLY after we've reached the end of the Linked List (The base case), 
            For example, the first time we reach this code is when current is the node before the tail and after is the tail.*/
    }
    

    };


Log in to reply
 

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