一、原题

Sort List

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

二、分析

快速排序和归并排序的时间复杂度是O(nlogn)。如果使用归并排序，在使用链表的情况下，不需要重新申请空间存放排序后的数组，可以做到空间复杂度数O(1)。我在这里使用归并排序来排序链表。

三、代码（java）

<pre name="code" class="java">/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public  ListNode sortList(ListNode head){
        if(head==null)
        return null;
	head=mergesort(head);
	return head;
}
public  ListNode  mergesort( ListNode start){
	if(start.next==null)
		return start;
	ListNode p1,p2,pre;

	p1=p2=pre=start;
	while(p1!=null){    //将原链表分成等长的两部分
		if(p1.next!=null){
		p1=p1.next.next;
		pre=p2;
		p2=p2.next;//p2就是中点
		}
		else break;
	}
	pre.next=null;
	
	start=mergesort(start);
	p2=mergesort(p2);
	start=merge(start,p2);
	return start;
}
public  ListNode merge(ListNode l1,ListNode l2){
	ListNode start,temp,pre;
	pre=new ListNode(0);
	if(l1.val<=l2.val)
		start = l1;
	else
		start = l2;
	temp=null;
	while((l1!=null)&&(l2!=null)){
	 if(l1.val<=l2.val){
		 pre.next=l1;
		 temp=l1.next;
		 l1.next=l2;
		 l1=temp;
         pre=pre.next;
	 }
	 else{
		 pre.next=l2;
		 temp=l2.next;
		 l2.next=l1;
		 l2=temp;
         pre=pre.next;
	 }
	}
    return start;
}
}

【Leetcode】Sort List解答