O(N)time, O(1) space clear Java solution with description


  • 2
    Z
    /**
     * Time complexity: In-order --> O(N)
     * Memory complexity: In-place --> O(1)
     * 
     */
    
    public ListNode reverseBetween(ListNode head, int m, int n) {
        
        //EDGE CASE
        if(head==null || head.next==null || m==n) return head;
        
        //INIT NODES
        //CONSIDER EDGE CASE WHEN M=1
        ListNode prev = (m==1)?head:null;
        ListNode cur = head;
        ListNode next = head.next;
        int pos = 1;
        
        //POS<M --> MOVE PREV,CUR,NEXT FORWARD BY 1
        //M<=POS<N --> PREV STOP MOVING, DO ROTATION BETWEEN CUR AND NEXT, THEN MOVE THEM FOWARD BY 1
        //POS==N --> BREAK THE LOOP, AND NOW, CUR IS AT THE "N"TH PLACE.
        while(cur!=null){
            if(pos<m){
                prev = cur;
                cur = next;
                next = next.next;
            }else if(pos>=m && pos<n){
                ListNode temp = next.next;
                next.next = cur;
                cur = next;
                next = temp;
            }else{
                break;
            }
            pos++;
        }
        
        //RE-LINK NODES 
        if(m==1){
            prev.next = next;
            return cur;
        }else{
            prev.next.next = next;
            prev.next = cur;
            return head;
        }
    }

Log in to reply
 

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