题解 | #单链表的排序#

思路，快速排序。

第一步，拿到第一个元素。

第二步，剩下的元素依次跟第一个比较，小的放在left，大的放在right，将链表分成了两段。

第三步，对分出来的left和right分别排序，然后组装起来返回即可。

代码如下：

import java.util.*;

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

public class Solution {
    /**
     *
     * @param head ListNode类 the head node
     * @return ListNode类
     */
    public ListNode sortInList (ListNode head) {
        /**
        快速排序
         */

         return sort(head);
    }


    public ListNode sort( ListNode head ) {
        if (head == null) {
            return null;
        }

        ListNode h = head.next;
        ListNode left = new ListNode(0);;
        ListNode right = new ListNode(0);

        while ( h != null ) {
            if (head.val >= h.val) {
                ListNode temp = left.next;
                left.next = h;
                h = h.next;
                left.next.next = temp;
            } else {
                ListNode temp = right.next;
                right.next = h;
                h = h.next;
                right.next.next = temp;
            }
        }

        left = sort(left.next);
        right = sort(right.next);
        ListNode tail = findTail(left);
        if(tail==null){
            head.next = right;
            return head;
        } else {
            tail.next = head;
            head.next = right;
            return left;
        }
    }

    public ListNode findTail( ListNode head ){
        if(head==null) return null;

        while(head.next!=null){
            head = head.next;
        }
        return head;
    }



}