4ms C++, linear, easy to understand, with thorough explanation


  • 0
    C
    /* The idea:
     * 1. break the list into 3 logical pieces, [1, m-1], [m, n] and [n+1, <end>]
     * 2. run a standard reverse algorithm on the [m, n] sub-list
     * 3. fix the wiring between the sub-lists
     */
     
    class Solution {
    public:
        /* This is basically a standard linked-list reversal algorithm, with 2 extra arguments.
         * What it does is starting from 'head' node, reverse the following 'count' nodes,
         * store the 'next' node of our last element (which basically means the node at '[count+1]')
         * as an output argument, then return the new head of our reversed sub-list (the node at '[count]').
         */
        ListNode *reverseSubList(ListNode *head, int count, ListNode **next) {
            if (!head) {
                return NULL;
            }
            if (count <= 1) {
                return head;
            }
            
            ListNode *prev = NULL;
            ListNode *curr = head;
            
            int i = 0;
            while (curr && i<count) {
                *next = curr->next;
                curr->next = prev;
                prev = curr;
                curr = *next;
                ++i;
            }
            
            return prev;
        }
        
        ListNode *reverseBetween(ListNode *head, int m, int n) {
            if (!head) {
                return NULL;
            }
            if (m == n) {
                return head;
            }
            
            // Use pointer-to-pointer trick to re-wire the 'head' later.
            ListNode **prev = &head;
            ListNode *curr = head;
            
            // Loop until we reach the m-th element.
            int i = 1;
            while (curr && i<m) {
                prev = &curr->next;
                curr = curr->next;
                ++i;
            }
            
            // Call our sub-routine to reverse the sub-list in range [m, n].
            ListNode *next = NULL;
            curr = reverseSubList(curr, n-m+1, &next);
            
            /* Now we have 3 logically separated lists, [1, m-1], [m, n] and [n+1, <end>].
             * The [m, n] list has been reversed, but the wiring between the 3 lists
             * are still broken, we need to fix that.
             *
             * The state of our variables:
             * 'prev': points to a pointer, which in-turn points to our element at [m-1]
             *          (if m==1, 'prev' points to the 'head' pointer of the entire list)
             * 'curr': points to element at [n]
             * 'next': points to element at [n+1]
             *
             * The fix is trivial:
             * 1. Connect [m, n] list to [n+1, <end>] list.
             *    The [m, n] list has been reversed, so the last element is [m], how do we
             *    get access to this element? Note we have 'prev' point to element [m-1],
             *    and the 'next' pointer of [m-1] never gets altered, so '[m-1]->next' still
             *    points to [m]. And we also have 'next' points to [n+1], so this fix is easy.
             * 2. Connect [1, m-1] list to [m, n] list.
             *    We have 'prev' points to [m-1] and 'curr' points to [n], so this fix is easy too.
             */
            (*prev)->next = next;
            *prev = curr;
            
            // if m==1, we have a new head stored in 'curr'
            // if m>1, the head is unchanged
            return m == 1 ? curr : head;
        }
    };

Log in to reply
 

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