Two while loops with explanation


  • 0
    R

    Two while loops solve the problem, with some explanations below:

    public ListNode reverseBetween(ListNode head, int m, int n) {
            if (head == null) return head;
    
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode cur = dummy;
            ListNode last = null;
            int i = 0;
    
            while (i < m) {
                last = cur; // reserve the last pointer
                cur = cur.next;
                i++;
            } // found the start -- cur
    
            ListNode tempLast = null;
            ListNode tobeTail = cur; // will become the tail after flip
            if (i == n) return dummy.next; // m could be equal to n
    
            // note: i <= n, not i < n !
            // below while loop is the same as in ReverseList !
            while (i <= n && cur != null) {
                ListNode newNext = cur.next;
                cur.next = tempLast;
                tempLast = cur;
                cur = newNext;
                i++;
            }
    
            // now: 1 -> 2 <- 3 <- 4 -> 5 (last node is 1 in this case, tobeTail is 2, cur is 5)
            last.next = tempLast; // this is to reverse the link, and connect the tail
            // now: 1 -> 4 -> 3 -> 2
            tobeTail.next = cur; // link to the real tail (which is cur [5])
            // now: 1 -> 4 -> 3 -> 2 -> 5
    
            return dummy.next;
        }
    
    

Log in to reply
 

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