My simple C++ solution (8ms accepted)


  • 1
    S

    Here's my C++ code. Took 8ms to pass. The idea is simple. First think about how we do in-order linked list reversal. We just need to be careful how we deal with rewiring the pointer when the counter hits n. I use a variable called "leftend" to rewire the pointers. I'd appreciate any feedbacks on my implementation.

    class Solution {
    public:
        ListNode *reverseBetween(ListNode *head, int m, int n) {
            if (head->next==NULL) return head;
            
            int counter = 0;
            ListNode* dummy = new ListNode(-1);
            dummy->next = head;
            ListNode* prev = NULL, *cur  = NULL, *next = NULL, *leftend = NULL, *oldhead = head;
            cur = dummy;
            
            while (counter <= n){
                if (counter >= m+1 && counter <= n){
                    next = cur->next;
                    cur->next = prev;
                    prev = cur;
                    cur  = next;
                } else {
                    if (counter == m-1) leftend = cur;
                    prev = cur;
                    cur  = cur->next;
                }
                counter++;
            }
            
            if (n>m){
                leftend->next->next = cur;
                leftend->next = prev;
            }
            
            if (m==1) return leftend->next;
            return oldhead;
        }
    };

  • 0
    A

    8ms?Are you sure? My subbmission with your code costs 40ms. And my AC solution is like yours using
    "new" which cost much time.


Log in to reply
 

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