Sort a linked list using insertion sort.
复杂度 o（n^2）;
设有一组关键字｛K1， K2，…， Kn｝；排序开始就认为 K1 是一个有序序列；让 K2 插入上述表长为 1 的有序序列，使之成为一个表长为 2 的有序序列；然后让 K3 插入上述表长为 2 的有序序列，使之成为一个表长为 3 的有序序列；依次类推，最后让 Kn 插入上述表长为 n-1 的有序序列，得一个表长为 n 的有序序列。
具体算法描述如下：
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode insertionSortList(ListNode head) { if(head == null || head.next == null) return head; ListNode dummy = new ListNode(0); ListNode pre = dummy; ListNode cur = head; while(cur != null){ ListNode next = cur.next; while( pre.next != null && pre.next.val < cur.val){ pre = pre.next; } //insert cur nodein pre and pre.next; cur.next = pre.next; pre.next = cur; pre = dummy; cur = next; } return dummy.next; } }
原文：http://www.cnblogs.com/joannacode/p/6009908.html