1 /** 2  * Definition for singly-linked list. 3  * public class ListNode { 4  *     int val; 5  *     ListNode next; 6  *     ListNode(int x) { 7  *         val = x; 8  *         next = null; 9  *     }10  * }11  */12 public class Solution {13     public ListNode insertionSortList(ListNode head) {14         if(head==null||head.next==null)15             return head;16         ListNode dummy=new ListNode(-1);17         ListNode pre,next;18         while(head!=null){19             pre=findPosition(dummy,head.val);20             next=pre.next;21             pre.next=new ListNode(head.val);22             pre.next.next=next;23             head=head.next;24         }25         return dummy.next;26     }27 28     private ListNode findPosition(ListNode dummy, int val) {29         // TODO Auto-generated method stub30         ListNode pre=dummy, next=pre.next;31         while(next!=null&&next.val<=val){32             next=next.next;33             pre=pre.next;34         }35         return pre;36     }37 }