c++ O(n)


  • 0
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        ListNode* reverseBetween(ListNode* head, int m, int n) 
        {
            int count;
            ListNode *prev = NULL,*next,*prev_m_1=NULL,*curr=head;
            
            count = m-1;
            
            if(m==n)
                return head;
                
            while(count)
            {
                prev_m_1 = curr;
                curr = curr->next;
                count--;
            }
            count = n - m + 1;
            while(count)
            {
                //cout << curr->val<< endl;
                next       = curr->next;
                curr->next = prev;
                prev       = curr;
                curr       = next;
                count--;
            }
            
            if(prev_m_1)
            {
                prev_m_1->next->next = curr;
                prev_m_1->next       = prev;
                
                return head;
            }
            
            head->next = curr;        
            return prev;
        }
    };
    

Log in to reply
 

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