Sort a linked list in O(n log n) time using constant space complexity.
题意：常数级别的空间复杂度、O(n log n) 的时间复杂度对链表排序。
思路：对链表进行归并排序。
- 待排序的链表如果是null或者只有一个节点，则直接返回。
- 找到链表的中间节点。
- 对左右两段继续递归进行排序。
- 将排序好的两段合并成一个链表。
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
//找middle
ListNode middle = findMiddle(head);
//拆两段
ListNode right = middle.next;
middle.next = null;
//对两段分别再进行sort
ListNode left = sortList(head);
right = sortList(right);
//merge两段
return merge(left, right);
}
public ListNode findMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head.next;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public ListNode merge(ListNode left, ListNode right) {
ListNode root = new ListNode(0);
ListNode dummy = root;
while (left != null || right != null) {
if (left == null) {
dummy.next = right;
right = right.next;
} else if (right == null) {
dummy.next = left;
left = left.next;
} else {
if (left.val < right.val) {
dummy.next = left;
left = left.next;
} else {
dummy.next = right;
right = right.next;
}
}
dummy = dummy.next;
}
return dummy.next;
}