Simple solution in Java


  • 0
    Y

    In-place and one pass solution to reverse nodes between m and n; need to consider m == 1 or not;

     public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null || m==n) return head;//do not need to reverse
        ListNode mNode = head, pre = null;
        int k = 1;
        ListNode p = head;
        ListNode newHead = null;
        while(k <= n){
            if(m > 1 && k == m-1){// find the m-th node and the previous node of m-th node;
               pre = p;
               mNode = p.next;
               p = p.next;
            }else if(k>=m && k<=n){//start to reverse nodes between m and n
                ListNode next = p.next;
                p.next = newHead;
                newHead = p;
                p = next;
            }else{
                p = p.next;
            }
            k++;
        }
        mNode.next = p; //after reverse, mnode now is the end of the reversed linkedlist, connect it to the n+1 node
        if(m==1){//means pre = null, reverse from the first node, and  newhead becomes head now
            head = newHead;
        }else{
            pre.next = newHead;//after reverse, new head now become the mNode;
        }
        return head;
      
    }

Log in to reply
 

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