https://oj.leetcode.com/problems/insertion-sort-list/
http://blog.csdn.net/linhuanmars/article/details/21144553
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode insertionSortList(ListNode head)
{
if (head == null || head.next == null)
return head;
// Add dummy head
ListNode dummyhead = new ListNode(0);
ListNode pre;
ListNode cur = head;
while(cur!=null)
{
ListNode next = cur.next;
pre = dummyhead;
while(pre.next!=null && pre.next.val<=cur.val)
pre = pre.next;
cur.next = pre.next;
pre.next = cur;
cur = next;
}
return dummyhead.next;
}
}[LeetCode]147 Insertion Sort List
原文：http://7371901.blog.51cto.com/7361901/1600822