Java solution with less pointers and detailed comments


  • 4
    public ListNode reverseBetween(ListNode head, int m, int n) {
            if(head == null) return head;
            ListNode fake_head = new ListNode(0);
            fake_head.next = head;
            
            //move to the start point
            ListNode pre = fake_head;
            for(int i = 0; i < m - 1; i ++){
                pre = pre.next;
            }
            
            //do the reverse
            ListNode cur = pre.next;
            ListNode new_head = null;
            for(int i = 0; i <= n - m; i ++){
                ListNode next = cur.next;
                cur.next = new_head;
                new_head = cur;
                cur = next;
            }
            
            //reconnect
            pre.next.next = cur;
            pre.next = new_head;
            
            return fake_head.next;
        }
    

  • 0

    really good one, except the reconnect part may be not that easy to understand LOL


  • 0
    P

    Hey...this one really looks good...except for the reconnect part...would you mind explaining that in a line or two? Thanks

    //reconnect
    pre.next.next = cur;
    pre.next = new_head;


  • 0

    In fact we don't need fake head

    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.