Insertion Sort List

 1 public class Solution {
 2     public ListNode insertionSortList(ListNode head) {
 3         // IMPORTANT: Please reset any member data you declared, as
 4         // the same Solution instance will be reused for each test case.
 5         ListNode prehead = new ListNode(0);
 6         ListNode runner = head;
 7         while(runner != null){
 8             ListNode tmp = runner.next;
 9             insertNode(prehead, runner);
10             runner = tmp;
11         }
12         return prehead.next;
13     }
14     
15     private void insertNode(ListNode head, ListNode node){
16         ListNode runner = head.next;
17         while(runner!=null){
18             if(runner.val >= node.val)
19                 break;
20             runner = runner.next;
21             head = head.next;
22         }
23         head.next = node;
24         node.next = runner;
25     }
26 }