My java solution 190ms, o(n), is this fast?


  • 0
    M
    public class Solution {
    private int rotateTime;
    private int count = 0;
    public ListNode reverseBetween(ListNode head, int m, int n) {
        rotateTime = (n - m + 1) / 2;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode i = dummy, j = dummy;
        do {
            m--;
            n--;
            if (m <= 0) {
                startRecurse(n, i, j);
            } else {
                i = i.next;
                j = j.next;
            }
        } while (m > 0);
        return dummy.next;
    }
    
    private ListNode startRecurse(int n, ListNode i, ListNode j) {
        if (n <= 0) {
            rotate(i, j);
            count++;
            return i.next;
        }
        
        ListNode left = startRecurse(--n, i, j.next); // divide
        if (count >= rotateTime) {              // backtrace
            return null;
        } else {
            rotate(left, j);
            count++;
            return left.next;
        }
    }
    
    private void rotate(ListNode i, ListNode j) {
        if (i.next == j) {
            ListNode inext = i.next;
            ListNode jnextnext = j.next.next;
            i.next = j.next;
            i.next.next = inext;
            i.next.next.next = jnextnext;
        } else {
            ListNode iafter = i.next;
            ListNode jafter = j.next;
            ListNode iafterafter = i.next.next;
            ListNode jafterafter = j.next.next;
            
            i.next = jafter;
            jafter.next = iafterafter;
            j.next = iafter;
            iafter.next = jafterafter;
        }
        return;
    }
    

    }


Log in to reply
 

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