Clean-Java-Solution


  • 0
    N
    public ListNode reverseBetween(ListNode head, int m, int n) {
            if (head == null || head.next == null || m == n) {
    			return head;
    		}
    
    		// Cut the linked list into 3 parts and save pointers
    		ListNode dummy = new ListNode(0);
    		dummy.next = head;
    
    		ListNode beforeTail = null;
    		ListNode beforeHead = null;
    		ListNode afterHead = null;
    		ListNode traverse = dummy;
    		Integer count = 1;
    
    		while (traverse != null) {
    			if (count == m) {
    				beforeTail = traverse;
    			}
    
    			if (count == (n + 1)) {
    				afterHead = traverse.next;
    				traverse.next = null;
    				break;
    			}
    
    			count++;
    			traverse = traverse.next;
    		}
    
    		beforeHead = beforeTail.next;
    		beforeTail.next = null;
    		ListNode reverseHead = reverseLinkedList(beforeHead);
    
    		// construct the linked list by joining all the parts
    		beforeTail.next = reverseHead;
    		traverse = reverseHead;
    
    		while (traverse.next != null) {
    			traverse = traverse.next;
    		}
    
    		traverse.next = afterHead;
    
    		return dummy.next;
        }
        
        private ListNode reverseLinkedList(ListNode head) {
    		if (head == null || head.next == null) {
    			return head;
    		}
    
    		ListNode p1 = head;
    		ListNode p2 = head.next;
    		head.next = null;
    
    		while (p2 != null) {
    			ListNode temp = p2.next;
    			p2.next = p1;
    			p1 = p2;
    			p2 = temp;
    		}
    
    		return p1;
    	}
    

Log in to reply
 

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