链表排序

题目需求

/**
* 在 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;
 }