AUG!!! Solution in JAVA, Clean Structure with Clean EXPLAINATION


  • 0
    /**
     * General Idea: eg.1->2->3->4->5 and m = 2 n = 4
     * We want to get 1 ->4->3->2->5
     * We can find out that we need to do two things,
     *  1 keep the order of nodes out of range [2,4]
     *  2 reverse the order of nodes in position [2,4]
     *  To do that, we need three new nodes to mark the position of nodes including 
     *  the previous node(m - 1) before position m, the first node(n) in range [m,n] 
     *  and the last node[n] in range[m,n]
     *  After doing that, we can redirect the next of  previous node to last,
     * next of first node to last's next And then, reverse the order between [m, n] 
     */
    public class Solution {
        public ListNode reverseBetween(ListNode head, int m, int n) {
                    ListNode first = null;
    		ListNode last = null;
    		ListNode pre = null;
    		ListNode hd = head;//Always copy a head for later use in ListNode preblem
    		
    		for(int i = 1; i <= n; i++)
    		{
    			if(i == m - 1)//find the previous node
    				pre = hd;
    				
    			else if(i == m)//find the first node
    				first = hd;
    				
    			if(i == n)//find the last node, it does not matter if n == m
    			{
                                     last = hd;
                                     break;//   after finding the last node, we can stop
                            }
    				
    			hd = hd.next;//move to next
    		}
    		
    		ListNode curr = first.next;
    		hd = head;
    		if(pre == null)//if pre == null, which means m == 1, the head node after reverse should be the last node in [m,n]
    			head = last;
    		else//if pre != null head is the same with the original list
    			pre.next = last;
    		
    		first.next = last.next;
    		for(int i = 0; i < n - m; i++)//The following is to reverse the order between [m,n]
    		{
    			ListNode next = curr.next;
    			curr.next = first;
    			first = curr;
    			curr = next;
    		}
    		return head;
        }
        
    }
    

    Like it? thumb up for me or leave you comment to communicate


Log in to reply
 

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