题解 | #单链表的排序#

插入排序O(n ^ 2)

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) {
        // write code here
        if(head == null) return null;
        if(head.next == null) return head;
        ListNode cur = head.next , ans = new ListNode(head.val);
        while(cur != null) {
            ListNode th = ans , pre = null;
            if(cur.val <= th.val) {
                ListNode temp = new ListNode(cur.val);
                temp.next = ans;
                ans = temp;
            }else {
                while(th != null && cur.val > th.val) {
                    pre = th;
                    th = th.next;
                }
                pre.next = new ListNode(cur.val);
                pre.next.next = th;
            }
            cur = cur.next;
        }
        return ans;
    }
}