Sort a linked list using insertion sort.
解题思路:
插入排序,JAVA实现如下:
public ListNode insertionSortList(ListNode head) {
if(head==null||head.next==null)
return head;
ListNode root=new ListNode(Integer.MIN_VALUE);
root.next=head;
head=head.next;
root.next.next=null;
ListNode temp=root,temp2=root;
L1:while(head!=null){
temp=root;
while(head.val>temp.next.val){
temp=temp.next;
if(temp.next==null){
temp.next=head;
head=head.next;
temp.next.next=null;
continue L1;
}
}
temp2=head;
head=head.next;
temp2.next=temp.next;
temp.next=temp2;
}
return root.next;
}