147. Insertion Sort List

Leetcode Linked List Sort

Sort a linked list using insertion sort.

A graphical example of insertion sort. The partial sorted list (black) initially contains only the first element in the list. With each iteration one element (red) is removed from the input data and inserted in-place into the sorted list

Algorithm of Insertion Sort:

• Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
• At each iteration, insertion sort removes one element from the input data, finds the location it belongs within the sorted list, and inserts it there.
• It repeats until no input elements remain.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

分析

这道题目非常直接，告诉了我们使用的算法-插入排序。但是唯一的区别是这里要排序的数据是链表。最直接的想法是把链表转换为数组，然后排序，然后再还原为链表。

public ListNode insertionSortList(ListNode head) {

    // the length of the Linkedlist
    int size = 0, i = 0, j = 0;
    ListNode curList = head;
    while (curList != null) {
        curList = curList.next;
        size++;
    }

    // special occasion
    if (size < 2) return head;

    // convert LinkedList to an array
    ListNode[] array = new ListNode[size];
    curList = head;
    while (curList != null) {
        array[i++] = curList;
        curList = curList.next;
    }

    // insertion sort the array
    for (i = 1; i < array.length; i++) {
        j = i;
        while (j > 0 && array[j].val < array[j-1].val) {
            curList = array[j];
            array[j] = array[j-1];
            array[j - 1] = curList;
            j--;
        }
    }

    // reconstruct linkedlist
    ListNode res = array[0];
    curList = res;
    for (i = 1; i < array.length - 1; i++) {
        curList.next = array[i];
        curList = curList.next;
    }
    curList.next = array[array.length - 1];
    curList.next.next = null;
    return res;
}

当然这种来回的转换其实是非常慢的。有没有一种方法可以直接插入排序呢？有的。这种方法利用了链表的一个特点 -- 可以在任意位置插入或者删除一个元素。当用插入排序数组时，我们依次和前面的元素比较，当发现前面的元素大与当前元素时，交换这两种元素，直到前面的元素都小与该元素，这时候该元素就插入到了正确位置。问题是链表需要一一交换吗？根本不需要！既然可以在任意位置删除，只需要一直比较前面的元素，直到发现正确的位置，然后插入到该位置即可。[ref]

public ListNode insertionSortList(ListNode head) {

    if (head == null || head.next == null)
    {
        return head;
    }

    ListNode sortedHead = head, sortedTail = head;
    head = head.next;
    sortedHead.next = null;

    while (head != null)
    {
        ListNode temp = head;
        head = head.next;
        temp.next = null;

        // new val is less than the head, just insert in the front
        if (temp.val <= sortedHead.val)
        {
            temp.next = sortedHead;
            sortedTail = sortedHead.next == null ? sortedHead : sortedTail;
            sortedHead = temp;
        }
        // new val is greater than the tail, just insert at the back
        else if (temp.val >= sortedTail.val)
        {
            sortedTail.next = temp;
            sortedTail = sortedTail.next;
        }
        // new val is somewhere in the middle, we will have to find its proper
        // location.
        else
        {
            ListNode current = sortedHead;
            while (current.next != null && current.next.val < temp.val)
            {
                current = current.next;
            }

            temp.next = current.next;
            current.next = temp;
        }
    }

    return sortedHead;
}