4ms one pass C++ solution


  • 2
    C

    My algorithm stops at the node before mth and nth node. p1 points to mth node. head2 is the beginning of the mth node. We reverse the mth node to nth node and keep track of nodes between m and n by using a counter (cnt).

    class Solution {
    public:
        ListNode *reverseBetween(ListNode *head, int m, int n) {
            
            if (m == n) return head;
            
            int cnt = 1;
            ListNode *p1, *p2, *tail;
            ListNode Dummy(0);
            Dummy.next = head;
    
            // p1 points to mth node
            for (p1=&Dummy; p1; ) {
                if (cnt == m)
                    break;
                p1 = p1->next;
                cnt++;
            }
            
            // head2 (points to mth node) is the beginning of the reverse list
            ListNode *head2 = p1->next;
            p2 = head2->next;
            tail = head2;
            
            // reverse list from m to n
            while (p2) {
                if (cnt == n)
                    break;
                ListNode *t = p2->next;
                p2->next = head2;
                tail->next = t;
                head2 = p2;
                p2 = t;
                cnt++;
            }
    
            // concatenate two lists
            p1->next = head2;
    
            return Dummy.next;
        }
    };

  • 0
    U

    I am not sure this is correct: after reversion, mth node should points to the element which is previously pointed by nth element, but I don't find this in the code. I appreciate any tips on this.


Log in to reply
 

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