给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
进阶：
你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？
示例 1：
输入：head = [4,2,1,3]
输出：[1,2,3,4]
示例 2：
输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]
示例 3：
输入：head = []
输出：[]
解法一：过笔试法：使用优先级队列将所有数以小根堆形式存储，再每次出节点元素进行拼接
class Solution { public ListNode sortList(ListNode head) { if(head==null) return null; PriorityQueue<ListNode> q = new PriorityQueue<>((x,y)->x.val-y.val); ListNode cur = head; while(cur!=null) { q.add(cur); cur = cur.next; } ListNode N = new ListNode(-1); ListNode node = N; while(!q.isEmpty()) { node.next = q.poll(); node = node.next; } node.next = null; return N.next; } }
解法二：二分递归排序（较优）
class Solution { public ListNode sortList(ListNode head) { if(head==null || head.next==null) return head; //归并排序方法，二分递归 //先找到链表的中点 ListNode fast = head.next; ListNode slow = head; while(fast!=null && fast.next!=null) { fast = fast.next.next; slow = slow.next; } //slow为中点，切割中点,分为左链表和右链表去递归 ListNode tep = slow.next; slow.next = null; ListNode left = sortList(head); ListNode right = sortList(tep); ListNode h = new ListNode(0); ListNode res = h; //再使用将两个排序链表合并成一个排序链表的操作 while(left!=null && right !=null) { if(left.val<right.val) { h.next=left; left = left.next; } else{ h.next = right; right = right.next; } h = h.next; } //最后肯定会有一个链表或两个链表走到尾 h.next = left!=null?left:right; return res.next; } }
原文：https://www.cnblogs.com/pionice/p/14515873.html