Simple java merge sort, commented.


  • 7
    J
     public ListNode sortList(ListNode head) {
    	if (head == null || head.next == null) return head;
    	
    	//Use two runners to break list into two halfs.
        ListNode fast = head, slow = head, prev = null;
        while (fast != null && fast.next != null) {
        	prev = slow;
        	slow = slow.next;
        	fast = fast.next.next;
        }
        ListNode second = prev.next;
        prev.next = null;
        //sort each half
        ListNode first = sortList(head);
        second = sortList(second);
        //merge them.
        head = mergeList(first, second);
        return head;
    }
    
    private ListNode mergeList(ListNode first, ListNode second) {
    	ListNode dummy = new ListNode(0), merged = dummy;
    	while (first != null && second != null) {
    		if (first.val <= second.val) {
    			merged.next = first;
    			merged = merged.next;
    			first = first.next;
    		} else {
    			merged.next = second;
    			merged = merged.next;
    			second = second.next;
    		}
    	}
    	if (first != null || second != null)
    		merged.next = (first != null)? first :second;
    	
    	return dummy.next;
    }

  • -4

    Your code has a serous defection !
    When you use two runners to break list into two halfs, the first part is much more longer than the other,so
    the alogrithm has the worst efficency!

    For example:
    Submission Result: Time Limit Exceeded More Details
    Last executed input:
    [8581,6131,9495,2797,105,3247,16943,16984,11099,-9031,-2956,-3444,9150,11509,-7 .......]


  • 0
    J

    Not sure I got your points. The code passed all test cases. Where did you the TLE from ? The code divides the list into perfect half and half for even length, and almost perfect for the odd length.


  • 0

    Yes,your java code answer is right!
    Maybe, it is caused by my python Code. I change your alogrithm to python Code!
    Thank you very much to pay attention my question!


  • 0
    B

    You are using recursvice calls, I don't think you achieve contant space with this since you are acutally storing O(n) calls to SortList()


  • 0
    D

    May I ask you why not divide the list from the beginning?Such as divide[1,4,2,3,7] into [1,4] &[2,3,7];and then divide[2,3,7] into [2,3]&[7]


Log in to reply
 

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