1 public class Solution { 2     public ListNode insertionSortList(ListNode head) { 3         int length = 0; 4         ListNode p = head; 5         while (p != null) { 6             length++; 7             p = p.next; 8         } 9 10         if (length <= 1) return head;11 12         ListNode[] list = new ListNode[length];13         p = head;14         for (int i = 0; i < list.length; i++) {15             list[i] = p;16             p  =p.next;17         }18 19         for (int i = 1; i < list.length; i++) {20             int j = i;21             while (j > 0 && list[j-1].val > list[j].val) {22                 ListNode temp = list[j-1];23                 list[j-1] = list[j];24                 list[j] = temp;25                 j--;26             }27         }28 29         for (int i = 0; i < list.length - 1; i++) {30             list[i].next = list[i+1];31             if (i == list.length - 2 ) {32                 list[i + 1].next = null;33             }34         }35 36         return list[0];37     38     }