Best Case Run Time : O(N)

Worst Case N方

Build the sorted list and insert each item into the previous sorted one. If it's an array could start comparing with the end sorted element (the biggest one) and switch under certain situation. If it is an linkedlist may need to start searching from the start because we cannot retrieve an item in linkedlist easily than in array

147. Insertion Sort List

Sort a linked list using insertion sort. 链表操作 在改变链接的时候注意保留现场

/**
 * 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) {
        if(head == null || head.next == null)return head;
        //because we need to use this dummy also as a comparison
        //thus we assign it the smallest value 
        ListNode dummy = new ListNode(Integer.MIN_VALUE);
        ListNode cur = head;
        while(cur != null){
            //keep the cur node next pointer for reference 
            ListNode next = cur.next;
            ListNode p = dummy;
            int val = cur.val;
            //break when we can find a range where we can put the 
            //current node 
            while(p.next != null){
                if(val >= p.val && val <= p.next.val){
                    break;
                }
                p = p.next;
            }
            //insert into the right location
            cur.next = p.next;
            p.next = cur;

            cur = next;
        }
        return dummy.next;
    }
}