插入排序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;
}
}