Insertion Sort List
Sort a linked list using insertion sort.
Given 1->3->2->0->null, return 0->1->2->3->null.
/** * Definition for ListNode. * public class ListNode { * int val; * ListNode next; * ListNode(int val) { * this.val = val; * this.next = null; * } * } */ public class Solution { /** * @param head: The first node of linked list. * @return: The head of linked list. */ public ListNode insertionSortList(ListNode head) { // write your code here ListNode dummy = new ListNode(Integer.MIN_VALUE); while (head != null) { ListNode curr = head; ListNode insert = dummy; while (insert.next != null && insert.next.val <= curr.val) { insert = insert.next; } head = head.next; curr.next = insert.next; insert.next = curr; } return dummy.next; } }