Java solution in 368 ms. A recursive solution whose performance is better than non-recursive.


  • 1
    L

    The recursive function "reverse_rec" (368ms) is better than the non-recursive one "reverse"(416ms), which is easy to read and even more efficient.

    private ListNode reverse_rec(ListNode start, int count){
    	if(count == 0 || start == null)
    		return start;
    
    	ListNode newTail = reverse_rec(start.next, count-1);
    	newTail.next = start;
    	start.next = null;
    	
    	return start;
    }
    
    private ListNode reverse(ListNode start, int count){
    	if(start == null || count <= 0)
    		return start;
    	
    	ListNode preNode, postNode;
    	
    	preNode = start;
    	postNode = preNode.next;
    	preNode.next = null;  // clear the link for the first element.
    	
    	while(count > 0){
    		ListNode next = postNode.next;
    		
    		// reverse the link
    		postNode.next = preNode;
    		count --;
    		
    		// move on to next pair.
    		preNode = postNode;
    		postNode = next;
    	}
    	
    	return preNode;
    }
    
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null)
        	return head;
        
        ListNode preNewTail = null, postNewHead = null; 
        ListNode newTail, newHead;
        ListNode iter = head;
        int count = n - m;
        
        if( --m == 0){
    		preNewTail = null;
    	}
    			
        while(n > 1){
        	
        	if(m == 1){
        		preNewTail = iter;
        	}
        	
        	iter = iter.next;
        	m --;
        	n --;
        }
        
        newHead = iter;
        postNewHead = newHead.next;
        
        if(preNewTail == null){
        	newTail = head;
        }else{
        	newTail = preNewTail.next;
        }
        
        //this.reverse(newTail, count);
        this.reverse_rec(newTail, count);
        
        newTail.next = postNewHead;
        
        if(preNewTail != null){
        	preNewTail.next = newHead;
        	return head;
        }else{
        	return newHead;
        }
    }

Log in to reply
 

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