LeetCode-链表插入排序

题目描述

Sort a linked list using insertion sort.

使用插入排序对链表排序，此处为单链表。

解题思路

插入排序就是依次将未排序部分的第一个元素插入到已排序部分合适的位置，使得已排序部分仍然有序。

列表可以直接根据位置索引元素，但是链表不可以直接取得指定位置的元素。

根据插入排序的思路：将整个链表按照已排序和未排序分为两部分，未排序部分的首个元素即为将要被排序的元素，问题变为将一个元素插入到一个有序链表中使得该链表仍然有序。分为两种情况：一种是合适位置在有序链表的非末尾，另一种是在有序链表的末尾，然后其他的问题就是注意插入时的赋值顺序。

代码实现

public ListNode insertionSortList1(ListNode head) {
    ListNode root = new ListNode(-1);
    while (head != null) {
        ListNode temp = root;
        while (temp.next != null && head.val >= temp.next.val)
            temp = temp.next;
        if (temp.next == null) {
            temp.next = head;
            head = head.next;
            temp.next.next = null;
        } else {
            ListNode temp2 = temp.next;
            temp.next = head;
            head = head.next;
            temp.next.next = temp2;
        }
    }
    return root.next;
}

参考：http://www.cnblogs.com/tonyluis/p/4579295.html