题解 | #单链表的排序#

import java.util.Arrays;
import java.util.ArrayList;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        // write code here
        if (null == head) {
            return null;
        }
        if (null == head.next) {
            return head;
        }
        // 定义一个数组，遍历链表，依次将链表中的每个值记录到数组里面去。然后，我们对数组进行快排。最终，重新将数组里面的值赋值到链表上去
        ArrayList<Integer> result = new ArrayList<>();
        // 定义一个辅助指针
        ListNode tp = head;
        while (null != tp) {
            result.add(tp.val);
            tp = tp.next;
        }
        tp = head;
        int[] rs = quickSort(result.stream().mapToInt(Integer::intValue).toArray());
        for (int i = 0; i < rs.length; i++) {
            tp.val = rs[i];
            tp = tp.next;
        }
        return head;
    }
    
    // 快排
    public static int[] quickSort(int[] array) {
        if (0 == array.length || 1 == array.length) {
            return array;
        }
        // 快排的具体实现
        // 荷兰国旗问题
        // 定义一个指针，该指针指向的是小于区域的边界
        int sp = -1;
        // 定义一个指针，该指针指向的是大于区域的边界
        int mp = array.length;
        // 定义一个指针，该指针指向的是当前遍历到的数组的位置
        int np = 0;
        // 定义一个整型变量，用于存放临时数据
        int tmp = 0;
        // 定义一个辅助变量，用于作为交换两个整型变量时的中间值
        int mid = 0;
        // 定义一个比较值，我们这里直接选取的是数组的最后一位上的数字
        int cv = array[array.length - 1];
        // 说明一下，由于我们选取的是数组中的一个数字作为比较值，所以小于区域和大于区域一定不会相遇。在这种情况下，我们选取的循环条件应该是 np != mp
        while (np != mp) {
            tmp = array[np]; // 获取当前位置上的数字
            if (tmp < cv) {
                // 如果小于比较值
                // 将小于区域的右移一位上的数字与该数字进行交换，同时小于区域向右扩充一位，np向右移动一位
                mid = array[np];
                array[np] = array[sp + 1];
                array[sp + 1] = mid;
                sp++;
                np++;
            }
            else if (tmp == cv) {
                np++; // np直接向右移动一位
            }
            else {
                // 如果大于比较值
                // 将大于区域的左移一位上的数字与该数字进行交换，同时大于区域向左扩充一位。注意，np不要动
                mid = array[np];
                array[np] = array[mp - 1];
                array[mp - 1] = mid;
                mp--;
            }
        }
        // 此时，我们解决了荷兰国旗问题
        // 接下来我们要做的事情很简单，就是对小于区域和大于区域也是用相同的处理方式(递归)
        int[] sr = quickSort(Arrays.copyOfRange(array, 0, sp + 1));
        int[] mr = quickSort(Arrays.copyOfRange(array, mp, array.length));
        // 将排好序的小于区域重新赋值到array数组中
        for (int i = 0; i < sr.length; i++) {
            array[i] = sr[i];
        }
        // 将排好序的大于区域重新赋值到array数组中
        for (int i = 0; i < mr.length; i++) {
            array[mp + i] = mr[i];
        }
        // 返回最终的结果
        return array;
    }
}