思路：快速排序。

  • 要求时间复杂度为 O(nlogn)，对我们选取的排序算法做出了限制，我们知道时间复杂度为 O(nlogn)的算法有快排、堆排序、归并排序。这里考虑使用快排。

复杂度

平均时间复杂度O(nlog n),空间发复杂度O(n)

图示

alt 代码（JAVA实现）

public class SOlution {
	public ListNode sortInList (ListNode head) {
        if(head==null||head.next==null) return head;//结点为空或只有一个结点
        return quickSort(head);
    }
	ListNode quickSort(ListNode head) {//链表快排，没有交换，排序稳定
		if(head==null||head.next==null) return head;//结点为空，或者只有一个结点
		//将链表分成三段，第一段都比枢轴小，第二段等于枢轴，第三段都大于枢轴
		ListNode lhead=new ListNode(-1);//第一段的虚头结点
      /* 这里提一下，注释里告诉我们ListNode类没有有参构造方法，但是new的新对象不加参数的话，
		 * 代码放到牛客编译器里出错，必须加上参数val才正常,这是牛客的一个疏忽吧
		 */
		ListNode mhead=new ListNode(-1);//第二段的虚头结点
		ListNode rhead=new ListNode(-1);//第三段的虚头结点
		ListNode left=lhead;//第一段的遍历指针
		ListNode mid=mhead;//第二段的遍历指针
		ListNode right=rhead;//第三段的遍历指针
		ListNode p=head;//原链表的遍历指针
		int pivot=head.val;//将第一个元素作为枢轴
		//不断划分
		while(p!=null) {
			if(p.val<pivot) {//比枢轴小，挂到第一段链表末尾
				left.next=p;
				left=left.next;
			}
			else if(p.val==pivot) {
				mid.next=p;
				mid=mid.next;
			}
			else {//比枢轴大，挂到第三段链表末尾
				right.next=p;
				right=right.next;
			}
			p=p.next;
		}
		left.next=null;//断开后面的链
		mid.next=null;//断开后面的链
		right.next=null;//断开后面的链
		
		//递归对第一段和第三段进行排序；因为第二段各元素相等，不用再排序
		lhead.next=quickSort(lhead.next);
		rhead.next=quickSort(rhead.next);
		left=getTail(lhead);//获取链表最后一个元素
		if(left!=null) left.next=mhead.next;//合并第一段和第二段
		mid=getTail(mhead);//获取链表最后一个元素
		if(mid!=null) mid.next=rhead.next;//合并第二段和第三段
		return lhead.next;
	}
	ListNode getTail(ListNode head) {//获取给定链表的最后一个结点
		if(head==null) return null;
		while(head.next!=null) {//不是最后一个结点就循环
			head=head.next;
		}
		return head;
	}
}