注意新的list跟原来的list是不相连的,然后把各个状态的点记录好就行:
public ListNode insertionSortList(ListNode head) { if (head == null || head.next == null) return head; //We started a new list here, not the original one ListNode dummy = new ListNode(0); ListNode curt = head, prev = dummy, next = head; while (curt != null) { next = curt.next; while (prev.next != null && prev.next.val < curt.val) { prev = prev.next; } curt.next = prev.next; prev.next = curt; curt = next; prev = dummy; } return dummy.next; }