题解 | #单链表的排序#

参考了一位大佬的博客：https://www.cnblogs.com/morethink/p/8452914.html 在一般实现的快速排序中，我们通过首尾指针来对元素进行切分，下面采用快排的另一种方法来对元素进行切分。

我们只需要两个指针p1和p2，这两个指针均往next方向移动，移动的过程中保持p1之前的key都小于选定的key，p1和p2之间的key都大于选定的key，那么当p2走到末尾时交换p1与key值便完成了一次切分。

//class ListNode {
//    int val;
//    ListNode next = null;
//
//    public ListNode(int i) {
//        this.val = i;
//    }
//}

public class Solution {
    /**
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode cur, tail = null;
        cur = head;

        //冒泡排序实现单链表排序
        while (cur.next != tail) {
            while (cur.next != tail) {
                if (cur.val > cur.next.val) {
                    int temp = cur.val;
                    cur.val = cur.next.val;
                    cur.next.val = temp;
                }
                cur = cur.next;
            }
            tail = cur;
            cur = head;
        }
        return head;
    }
    public static void main(String[] args){
        ListNode l1 = new ListNode(-1);
        ListNode l2 = new ListNode(5);
        ListNode l3 = new ListNode(3);
        ListNode l4 = new ListNode(4);
        ListNode l5 = new ListNode(0);
        l1.next = l2;
        l2.next = l3;
        l3.next = l4;
        l4.next = l5;
        l5.next = null;
        ListNode head = sortList(l1);

        while(head != null){
            System.out.print(head.val+" ");
            head = head.next;
        }
    }

    /**
     * 使用快速排序
     * @param head 待排序的单链表
     * @return ListNode
     */
    public ListNode sortInList(ListNode head) {
        //采用快速排序
        quickSort(head, null);
        return head;
    }
    public static void quickSort(ListNode head, ListNode end) {
        if (head != end) {
            //寻找基准点
            ListNode node = partion(head, end);
            //对基准点前面的小数序列排序
            quickSort(head, node);
            //对基准点后面的大数序列排序
            quickSort(node.next, end);
        }
    }

    public static ListNode partion(ListNode head, ListNode end) {
        ListNode p1 = head, p2 = head.next;

        //走到末尾才停
        while (p2 != end) {

            //后面的值比key值小时，p1向前走一步，交换p1与p2的值
            if (p2.val < head.val) {
                p1 = p1.next;

                int temp = p1.val;
                p1.val = p2.val;
                p2.val = temp;
            }
            p2 = p2.next;
        }

        //当有序时，不交换p1和key值
        if (p1 != head) {
            int temp = p1.val;
            p1.val = head.val;
            head.val = temp;
        }
        return p1;
    }

}