题目需求
/**
* 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。
* <p>
* 示例 1:
* <p>
* 输入: 4->2->1->3
* 输出: 1->2->3->4
* 示例 2:
* <p>
* 输入: -1->5->3->4->0
* 输出: -1->0->3->4->5
*/
解题思路
快排
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode end = head;
while (end.next != null) {
end = end.next;
}
qSort(head, end);
return head;
}
private void qSort(ListNode head, ListNode end) {
if (head == null || head == end || end == null) {
return;
}
ListNode p = partition(head, end);
qSort(head, p);
ListNode pNext = p.next == null ? p : p.next;
qSort(pNext, end);
}
private ListNode partition(ListNode head, ListNode end) {
if (head == null || end == head) {
return head;
}
ListNode pivot = end;
int pValue = pivot.val;
ListNode i = head, j = head;
ListNode retNode = head;
for (; j != null && j != end; j = j.next) {
if (j.val < pValue) {
int t = i.val;
i.val = j.val;
j.val = t;
retNode = i;
i = i.next;
}
}
end.val = i.val;
i.val = pValue;
return retNode;
}
