Insertion Sort List

public class Solution {
    public ListNode insertionSortList(ListNode head) {
        ListNode prehead = new ListNode(3);
        ListNode runner = head;
        while(runner != null){
            ListNode tmp = runner.next;
            insertNode(prehead, runner);
            runner = tmp;
        }
        return prehead.next;
    }
    // 将 node 插入到fake head的list中去
    private void insertNode(ListNode head, ListNode node){
        ListNode runner = head.next;
        while(runner!=null){
            //如果当前runner node的值比 node大，将node插入
            if(runner.val >= node.val)
                break;
            runner = runner.next;
            head = head.next;
        }
        head.next = node;
        node.next = runner;
    }
}