A different Java solution O(n) - reverse with style


  • 0
    O
    
        /**
         * Reverse with style.
         *
         * 1. Create a prev node and keep moving it until the mth node
         * 2. Any node after the mth node ( until n  ) , move that node next to the prev node.
         * Essentially, do the reverse by moving the node
         */
        public ListNode reverseBetween(ListNode head, int m, int n) {
            if(null == head){
                return null;
            }
    
            // short circuit, nothing to reverse.
            if(m == n){
                return head;
            }
    
            ListNode prevHead = new ListNode(0);
            prevHead.next = head;
            ListNode curPrev = prevHead;
            ListNode cur = head;
            int i = 1;
    
            // bring cur to the m'th Node.
            // Move the prev node such that
            // prev is one before cur.
            // Keep the previous head anchored at prevHead.
            while(i < m){
                i++;
                curPrev = cur;
                cur = cur.next;
            }
    
            // Mark the m'th node
            ListNode mh = cur;
            ListNode mc = cur;
    
            // move cur. Any node beyond this
            // needs to be reversed, until n
            cur = cur.next;
            i++;
            while (i <= n){
                i++;
                ListNode nxt = cur.next;
                curPrev.next = cur;
                cur.next = mc;
                mh.next = nxt;
                mc = cur;
                cur = nxt;
            }
            return prevHead.next;
    
        }
    
    
    

Log in to reply
 

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