6-10 lines in C++


  • 7

    Update 4:
    "Code golf" (6 lines)

    Not fully golfed, but yeah...

    ListNode* reverseBetween(ListNode *head, int m, int n) {
        ListNode **a = &head, **b;
        for (;m--; n--)
            a = &(*(b=a))->next;
        for (;n--; swap(*b, *a))
            swap(*b, (*a)->next);
        return head;
    }
    

    Update 3:
    Pointer pointers (8 lines)

    Removed duplicate code.

    ListNode* reverseBetween(ListNode *head, int m, int n) {
        ListNode **pivot = &head, **prev;
        for (int i=0; i<m; i++)
            pivot = &(*(prev=pivot))->next;
        for (int i=m; i<n; i++) {
            swap(*prev, (*pivot)->next);
            swap(*prev, *pivot);
        }
        return head;
    }
    

    Update 2:
    Pointer pointers (9 lines)

    Using a second pointer pointer.

    ListNode* reverseBetween(ListNode *head, int m, int n) {
        ListNode **prev = &head;
        for (int i=1; i<m; i++)
            prev = &(*prev)->next;
        ListNode **pivot = &(*prev)->next;
        for (int i=m; i<n; i++) {
            swap(*prev, (*pivot)->next);
            swap(*prev, *pivot);
        }
        return head;
    }
    

    Update 1:
    Pointer pointer (9 lines)

    Motivated by quick glance at lchen77's solution.

    ListNode* reverseBetween(ListNode *head, int m, int n) {
        ListNode **prev = &head;
        for (int i=1; i<m; i++)
            prev = &(*prev)->next;
        ListNode *pivot = *prev;
        for (int i=m; i<n; i++) {
            swap(*prev, pivot->next->next);
            swap(*prev, pivot->next);
        }
        return head;
    }
    

    Dummy node (10 lines)

    My original one.

    ListNode* reverseBetween(ListNode *head, int m, int n) {
        ListNode dummy(0), *prev = &dummy;
        dummy.next = head;
        for (int i=1; i<m; i++)
            prev = prev->next;
        ListNode *pivot = prev->next;
        for (int i=m; i<n; i++) {
            swap(prev->next, pivot->next->next);
            swap(prev->next, pivot->next);
        }
        return dummy.next;
    }

  • 0
    R

    Hello Stephan,
    Can you please explain what the second line is doing in this case? I am not able to wrap my head around the pivot = &(*(prev=pivot))->next; part.

    ListNode* reverseBetween(ListNode *head, int m, int n) {
        ListNode **pivot = &head, **prev;
        for (int i=0; i<m; i++)
            pivot = &(*(prev=pivot))->next;
        for (int i=m; i<n; i++) {
            swap(*prev, (*pivot)->next);
            swap(*prev, *pivot);
        }
        return head;
    }```

  • 0
    F

    The swap-loop is much harder to understand than the normal 4-assignments-loop. I prefer the simple one.

    But I'm still a little curious, is that what you normally do in real programming? and how long will you pause here to check and make sure every move is what you exactly want? 10 seconds? 5 minutes?

    I just spent 20 minutes to simulate on paper every possibility of the swap :D


  • 1
    S

    I'm curious about your job?How extraordinary! In fact, what I'm concerned about is the following: How do you come up with this method?Could you explain the details?


Log in to reply
 

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