Sort List

问题描述（难度中等）

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

方法一：递归归并排序

记录下时间复杂度分析吧，如何理解归并排序的时间复杂度。假设当前有m个数字待排序，需要被分成logm次，每个同等级的子问题需要m的时间去排序。总体的复杂度为m*logm。

延伸一下，大文件排序，如果1024M（m）的文件，内存只有8M（n）。计算一下时间复杂度。

• mlog(m/n)+(m/n)nlogn，即mlogm。

package P148;

import AddTwoNumbers.ListNode;
import CommonUtils.ListNodeUtils;

/**
 * 归并排序
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {

    public ListNode sortList(ListNode head) {
        if (head==null ||head.next == null) {
            return head;
        }
        //定位到中间位置
        ListNode fast=head;
        ListNode front;
        ListNode slow=head;
        while (true){
            front=slow;
            slow=slow.next;
            fast=fast.next.next;
            if (fast==null || fast.next==null ) {
                front.next=null;
                break;
            }
        }
        //返回子问题
        ListNode leftSort=sortList(head);
        ListNode rightSort=sortList(slow);

        return mergeTwoLinkedList(leftSort,rightSort);
    }

    public ListNode mergeTwoLinkedList(ListNode leftSort,ListNode rightSort){
        ListNode newHead=new ListNode(0);
        ListNode current=newHead;
        while (leftSort!=null || rightSort!=null){
            if (leftSort==null) {
                current.next=rightSort;
                break;
            }else if(rightSort==null){
                current.next=leftSort;
                break;
            }else {
                if ((leftSort.val<rightSort.val)) {
                    ListNode listNode=new ListNode(leftSort.val);
                    current.next=listNode;
                    current=listNode;
                    leftSort=leftSort.next;
                }else {
                    ListNode listNode=new ListNode(rightSort.val);
                    current.next=listNode;
                    current=listNode;
                    rightSort=rightSort.next;
                }
            }
        }
        return newHead.next;
    }

    public static void main(String[] args) {
        int[] ints={4,2,1,3};
        int[] ints1={-1,5,3,4,0};
        ListNode listNode= ListNodeUtils.buildWithArray(ints);
        ListNode testst1= ListNodeUtils.buildWithArray(ints1);

        new Solution().sortList(listNode);
        ListNodeUtils.printListNodes(new Solution().sortList(testst1));
        ListNodeUtils.printListNodes(null);
    }
}

总结

归并排序，递归排序，充分利用了递归的美感。