Sort a linked list using insertion sort.
对链表使用插入排序还是很简单的,从链表中拆下一个节点,然后把它插入到已经排序的部分的链表中,直到所有节点都被插入。代码如下:
1 public class Solution { 2 public ListNode insertionSortList(ListNode head) { 3 if(head==null || head.next==null) return head; 4 5 ListNode sorted = new ListNode(-1); 6 sorted.next = head; 7 head = head.next; 8 sorted.next.next = null; 9 10 while(head!=null){ 11 ListNode temp = head; 12 head = head.next; 13 ListNode sortpre = sorted; 14 ListNode sortcur = sorted.next; 15 while(sortcur!=null){ 16 if(temp.val<=sortcur.val){ 17 sortpre.next = temp; 18 temp.next = sortcur; 19 break; 20 } 21 else{ 22 sortpre = sortcur; 23 sortcur = sortcur.next; 24 } 25 } 26 if(sortcur==null){ 27 sortpre.next = temp; 28 temp.next = null; 29 } 30 } 31 32 return sorted.next; 33 } 34 }