[leetcode] Insertion Sort List

开一个新list, 然后逐个逐个把input的node 插到新list里面

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ public class Solution { public ListNode insertionSortList(ListNode head) { ListNode dummy = new ListNode(Integer.MIN_VALUE); while (head != null){ ListNode pre = dummy; ListNode next = dummy.next; ListNode current = head; head = head.next; while (next != null && next.val < current.val){ pre = next; next = next.next; } pre.next = current; current.next = next; } return dummy.next; } }