Java implementation with comments (accepted)


  • 0
    P

    I'd like to share my java implementation. The most triky part is insertion where where we change links.

    public ListNode insertionSortList(ListNode head) {
    		if (head == null) return null;
    		
    		ListNode sortTail = head;
    		ListNode unsortHead = head.next;
    		
    		while (unsortHead != null){
    			
    			ListNode sortHead = head;
    			ListNode sortHeadPre = null;
    			
    			// Search for a place to insert
    			while (sortHead.val < unsortHead.val && sortHead != unsortHead) {
    				sortHeadPre = sortHead;
    				sortHead = sortHead.next;
    			}
    			
    			// Insert
    			ListNode unsortNext = unsortHead.next;
    			if (sortHead != unsortHead) {
    				unsortHead.next = sortHead;
    				sortTail.next = unsortNext;
    				if (sortHeadPre == null) {
    					head = unsortHead;
    				} else {
    					sortHeadPre.next = unsortHead;
    				}
    			} else {
    				sortTail = sortHead;
    			}
    			unsortHead = unsortNext;
    		}
    		
    		return head;
    }

Log in to reply
 

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