题目

• 链表的插入排序

解法

• 先回顾一下数组中插入排序的做法：
• 首先是双层for循环，外层从i=0开始一直到数组最后一个结束，内层从i开始，然后依次递减直到a[j]>=a[j-1]结束循环（控制边界）
• 每次都需要将数组从前往后移位(交换位置)
• 依次下去完成整个插入排序
• 链表插入的思想和上述方法差不多，但是单链表只有指向后向链表，并没有指向index节点的前一个节点或者前n个节点的方法，我们在查找的时候就不如数组那样直接获取下标方便。
• 那么我们可以先假设现在要插入的链表节点是listi，那么我们需要从1~i-1中找到list[i]的合适插入点
• 我采取的方法就是从list[1]开始遍历直到找到一个节点list[x]比list[i]的val小，但后一个节点list[x+1].val比list[i].val值大，那么这二者之间就是list[i]需要插入的位置。
• 其次，链表的插入我们需要知道插入的前一个节点的索引才能执行，因此我们需要声明一个insertPre表示上述中list[x]索引，indexPre表示我们需要插入的list[i]的前一个索引，因为我们将list[i]插入到list[x]之后，此时需要将list[i]的前一个索引即indexPre的next指向list[i]的next，完成修改
• 同时为了避免插入到头节点中，我采取声明一个front节点，front.next指向head，front无实际意义只是为了方便我们将节点插入头结点中。

代码实现

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode insertionSortList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode front = new ListNode(0);
        front.next = head;
        ListNode index = head.next;
        ListNode indexPre = head;
        while (index != null) {
            ListNode insertPre = front;
            ListNode temp = front.next;
            while (temp.val < index.val) {
                insertPre = temp;
                temp = temp.next;
            }
            if (temp != index) {
                indexPre.next = index.next;
                index.next = insertPre.next;
                insertPre.next = index;
                index = indexPre.next;
            } else {
                indexPre = index;
                index = index.next;
            }
        }
        return front.next;
    }
}