Very Long Solutioni


  • 0
    W
    /**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
    
        ListNode* reverse (ListNode* head){
            ListNode* prev = NULL;
            ListNode* current = head;
            ListNode* next;
            while(current!=NULL){
                next = current->next;
                current->next = prev;
                prev = current;
                current = next;
            }
            head = prev;
            return head;
        }
        ListNode* reverseBetween(ListNode* head, int m, int n) {
            // we are protected as long as m!=1 and n !=last
            //find the sub list, reverse it, and then append it back;
            ListNode* new_head = head;
            if (m == 1){
                ListNode* sub_head = new_head;
                ListNode* sub_tail = new_head;
                for (int i=0;i<n-m;i++){
                    sub_tail = sub_tail->next;
                }
                if(sub_tail->next == NULL){
                    return reverse(sub_head);
                }else{
                    ListNode* new_tail = sub_tail->next;
                    sub_tail->next = NULL;
                    head = reverse(sub_head);
                    new_head->next = new_tail;
                    return head;
                }
                
                
            }else{
            for(int i=0;i<m-2;i++){
                new_head = new_head->next;
            }
            ListNode* sub_head = new_head->next;
            ListNode* sub_tail = new_head;
            for (int i=0;i<n-m+1;i++){
                sub_tail = sub_tail->next;
            }
                if(sub_tail->next == NULL){
                    new_head->next = reverse(sub_head);
                    return head;
                }else{
                    ListNode* new_tail = sub_tail->next;
                    sub_tail->next = NULL;
                    new_head->next = reverse(sub_head);
                    sub_head->next = new_tail;
                    return head;
                    
                }
    
            
        }
        }
    };
    

Log in to reply
 

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