148. Sort List

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

这道题要求用nlogn的时间复杂度去做，那么只有分治法了，这道题可以当作是把一个毛毛虫切成n段，所有的关节都给切掉，然后再把骨头重新排序装起来。代码如下：

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

public class Solution {

    public ListNode sortList(ListNode head) {

        if(head==null||head.next==null) return head;

        ListNode fast = head;

        ListNode slow = head;

        ListNode pre=null;

        while(fast!=null&&fast.next!=null){

            pre = slow;

            slow = slow.next;

            fast = fast.next.next;

        }

        pre.next = null;

        ListNode l1=sortList(head);

        ListNode l2=sortList(slow);

        return merge(l1,l2);

    }

    public ListNode merge(ListNode l1,ListNode l2){

        ListNode node = new ListNode(0);

        ListNode dummy = node;

        while(l1!=null&&l2!=null){

            if(l1.val<l2.val){

                ListNode next = new ListNode(l1.val);

                node.next = next;

                node =node.next;

                l1 = l1.next;

            }else{

                ListNode next = new ListNode(l2.val);

                node.next = next;

                node =node.next;

                l2 = l2.next;

            }

        }

        if(l1!=null){

            node.next = l1;

        }

        if(l2!=null){

            node.next = l2;

        }

        return dummy.next;

    }

}

148. Sort List

原文：http://www.cnblogs.com/codeskiller/p/6359949.html