Sort a linked list using insertion sort.
使用插入排序的方法排序链表
public class Solution {
public ListNode insertionSortList(ListNode head) {
if(head==null) return null;
ListNode start = new ListNode(0);
ListNode pre = start;//插入位置的前一个节点
ListNode cur = head;//当前要插的节点
ListNode next = null;//下一个要插的节点
while(cur!=null){
next = cur.next;
while(pre.next!=null && pre.next.val<cur.val) pre = pre.next;
cur.next = pre.next;
pre.next = cur;
pre = start;
cur = next;
}
return start.next;
}
}
