思路
- 先判斷邊界輸入貌嫡。
- 拆出一個鏈表元素，head指針移動岛抄，直到head為空。
- 拿拆出的元素與新建的排好序的鏈表比較夫椭，看插在哪里。有三種方式扰付，插在開頭感凤，插在中間，插在末尾陪竿。插入后把指針指到此鏈表開頭，跳出循環(huán)闰挡。
class Solution {
public ListNode insertionSortList(ListNode head) {
if(head==null||head.next==null)
return head;
ListNode p1 = new ListNode(-999);
ListNode p2 = p1;
ListNode p3 = p1;
while(head!=null){
ListNode tmp = new ListNode(head.val);
head = head.next;
if(p1.next==null){
p1.next = tmp;
continue;
}
while(p1.next!=null){
if(tmp.val<p1.next.val){
ListNode tmp1 = p1.next;
p1.next = tmp;
tmp.next = tmp1;
p1 = p2;
break;
}
else
p1 = p1.next;
}
if(p1.next==null){
p1.next = tmp;
p1 = p2;
}
}
return p3.next;
}
}
