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

大家看完题目估计跟我一样啦。。。都在想哪些是nlogn啊~快速排序、归并排序、堆排序！然后开始愁，这些东西变成list了可怎么办啊。。。

可是我深深地记得在CMU的时候老师告诉我，java现在自带的Arrays.sort用的是快排，然后我就想，那么……为什么不把list转成array然后排完了放回去呢！

于是我就用一个arraylist先装这个list，然后再把arraylist转成array去sort，然后把结果再存进一个linkedlist返回头结点~写到这里自己都想乐了，又笨又好玩的方法~

不说了，直接上代码~已通过leetcode测试~附带测试main函数

import java.util.ArrayList;
import java.util.Arrays;

public class sortList {
	public static void main(String args[]){
		sortList dp = new sortList();
		ListNode head  = new ListNode(3);
		ListNode p1 = new ListNode(2);
		head.next=p1;
		ListNode p2  = new ListNode(1);
		p1.next =  p2;
		ListNode p3 = new ListNode(5);
		p2.next = p3;
		ListNode p4 = new ListNode(4);
		p3.next = p4;
		prinf(head);
		prinf(dp.sortList(head));
	}
	
	private static void prinf(ListNode input){
		while(input!=null)	{
			System.out.print(input.val+"->");
			input = input.next;
		}
		System.out.println();
	}

<span style="white-space:pre">	</span>//下面犯贱开始
	public ListNode sortList(ListNode head) {//建议大家换个方法名或者class名，我这里重复了
		if(head==null)  return head;
        ArrayList<Integer> arr = new ArrayList<Integer>();
        int j=0;
        ListNode p= head;
        while(p!=null){
        	arr.add(p.val);
        	p=p.next;
        }
        Object[] array = arr.toArray();
        Arrays.sort(array);//其实只有这一步。。。
        ListNode start= new ListNode(0);
        ListNode q = start;
        for(int i=0;i<array.length;i++){
        	q.val=(Integer) array[i];
        	if(i==array.length-1)	{q.next = null;break;}
        	ListNode k = new ListNode(0);
        	q.next=k;
        	q=k;
        }
        return start;
    }
}

【Leetcode】Sort List in java，你绝对想不到我是怎么做的^^我写完过了我自己都觉得好jian~