6-10 lines in C++


  • 7

    This ended up a bit extreme. I suggest to read the original one at the bottom first, which also includes an explanation. Then move upwards through the updates.

    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;
    }
    

    Some explanation: First I find the node right before the first node in the reverse range. I call it prev. And I call the first node in the reverse range pivot. Then this pivot node goes through the reverse range. Every next node it encounters is moved behind prev, i.e., to the start of the reverse range.

    So before the reversing, I'm in this situation:

    prev   pivot
     |       |
    [A] --> [B] --> [C] --> [D] --> [E] --> [F] --> ...
    

    In front of the pivot we have node C, which gets moved to after prev, and pivot moves on:

    prev           pivot
     |               |
    [A] --> [C] --> [B] --> [D] --> [E] --> [F] --> ...
    

    So far the range from B to C has been reversed. If that was the goal, we can stop now. Otherwise... Now in front of the pivot we have node D, which gets moved to after prev, and pivot moves on:

    prev                   pivot
     |                       |
    [A] --> [D] --> [C] --> [B] --> [E] --> [F] --> ...
    

    So far the range from B to D has been reversed. If that was the goal, we can stop now. Otherwise... Now in front of the pivot we have node E, which gets moved to after prev, and pivot moves on:

    prev                           pivot
     |                               |
    [A] --> [E] --> [D] --> [C] --> [B] --> [F] --> ...
    

    So far the range from B to E has been reversed. If that was the goal, we can stop now. Otherwise...

    And so on...

    Note that taking out a node in front of the pivot and inserting it after prev involves modifying three pointers: prev->next, pivot->next and pivot->next->next. I do it with two swaps, but it could also be done with a helper variable and four assignments:

            for (int i=m; i<n; i++) {
                auto next = pivot->next;
                pivot->next = next->next;
                next->next = prev->next;
                prev->next = 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?


  • 0
    C

    I can't understand your code, it is really hard to understand !
    please tell me why !


  • 0

    @Carrot21 I just added some advice at the top and some explanation at the bottom. Hope that helps.


  • 0

    @forsaken said in 6-10 lines in C++:

    But I'm still a little curious, is that what you normally do in real programming?

    Hmm, I probably wouldn't. This ended up mostly as an exercise for using pointer pointers. Though I think they can indeed have advantages in "real" programming. I mean, Linus Torvalds seems to like them:
    https://grisha.org/blog/2013/04/02/linus-on-understanding-pointers/

    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

    I don't remember how long it took me and how I did it. And of course me writing it was the opposite direction of you reading it. You see my code and try to understand it. That is, you go from code to idea. Whereas I went from idea to code. I already knew what I wanted to do and just had to implement that in code. But I suspect I didn't write it directly like I showed above, not even the "original" version. More likely I started with the temporary-variable-and-four-assignments version. Which is a 3-cycle, which I know is equivalent to two swaps. And quite possibly I did draw it on paper as well. At least I did do that now in order to again understand my solution in order to explain it, because I had already forgotten what it does, i.e., forgotten the idea :-)

    Oh wait, right, we can see our submission history. So, here's what my first submission looked like (and it got accepted):

    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 *last = prev->next, *curr = last;
        for (int i=m; i<=n; i++) {
            ListNode *next = curr->next;
            curr->next = prev->next;
            prev->next = curr;
            curr = next;
        }
        last->next = curr;
        return dummy.next;
    }
    

    And my second submission was this:

    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 *last = prev->next;
        for (int i=m; i<n; i++) {
            swap(prev->next, last->next->next);
            swap(prev->next, last->next);
        }
        return dummy.next;
    }
    

    For the third submission I just renamed last to pivot and that's the "original one" I posted above.


Log in to reply
 

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