Simple java merge sort, commented.

  • 7
     public ListNode sortList(ListNode head) {
    	if (head == null || == null) return head;
    	//Use two runners to break list into two halfs.
        ListNode fast = head, slow = head, prev = null;
        while (fast != null && != null) {
        	prev = slow;
        	slow =;
        	fast =;
        ListNode second =; = 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) { = first;
    			merged =;
    			first =;
    		} else { = second;
    			merged =;
    			second =;
    	if (first != null || second != null) = (first != null)? first :second;

  • -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

    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

    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

    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.