**Understand the problem:**

The crux of the problem is to understand what is the insertion sort. Basically, the idea of the insertion sort is for a partially sorted list, say, A[] = {1 3 4 5}, and we wanna insert 2 to the list at an appropriate position. In general, the idea of the insertion sort is for a given point i, we wanna make sure its left noes are well sorted. How to achieve this? compare A[i] with A[i -1], if less, swap.

**Solution:**

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

## No comments:

## Post a Comment