Simple C++ recursive solution


  • 1
    S
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (m == n)
            return head;
        
        if (m > 1) {
            ListNode *node = head;
            for (int i = 1; i < m - 1; i++)
                node = node->next;
            ListNode *next = reverseBetween(node->next, 1, n - m + 1);
            node->next = next;
        }
        else {
            ListNode *tail = head;
            for (int i = 0; i < n; i++)
                tail = tail->next;
            ListNode *next = reverseBetween(head->next, 1, n - 1);
            head->next->next = head;
            head->next = tail;
            head = next;
        }
        
        return head;
    }
    

  • 0
    S

    Thank you for sharing. But I dont think this method is one-pass. Also, it takes O((n-m)^2) of time.


Log in to reply
 

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