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; } }