链表的插入排序

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head ListNode类 
     * @return ListNode类
     */
    public ListNode insertionSortList (ListNode head) {
        // write code here
        if(head == null || head.next == null) return head;
        ListNode node = new ListNode(head.val);
        ListNode headNext = insertionSortList(head.next);

        if(node.val <= headNext.val){
            node.next = headNext;
            return node;
        }

        ListNode cur = headNext;
        ListNode prev = new ListNode(-1);
        while(cur != null && cur.val < node.val){
            prev = cur;
            cur = cur.next;
        }
        if(cur == null){
            prev.next = node;
        }else{
            prev.next = node;
            node.next = cur;
        }
        return headNext;
    }
}