No dummy head O(n) solution~


  • 0
    public ListNode reverseBetween(ListNode head, int m, int n) {
        ListNode current = head, pre = null, breakNode = null;
        int i = 0;
        while(++i<m){ // go to breakNode, which is node m-1
            breakNode = current;
            pre = current;
            current = current.next;
        }
        while(i++<=n){// Reverse nodes from m to n
            ListNode next = current.next;
            current.next = pre;
            pre = current;
            current = next;
        }
        if(breakNode==null) { // incase of m = 1, we connect head with node n+1 and return node n;
            head.next = current; return pre;
        } 
        breakNode.next.next = current;  // breakNode.next is the node m, we connect it with node n+1;
        breakNode.next = pre;  // connect breakNode with node n;
        return head;
    }

Log in to reply
 

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