对链表进行插入排序（147）

题目

对链表进行插入排序。

插入排序算法

• 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
• 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
• 重复直到所有输入数据插入完为止。

算法

因为单链表不能向前查找，所以我们每次寻找插入点的时候都从前向后寻找插入点

• 如果是空链表或只有一个节点的链表，直接返回链表
• 先设置哨兵节点sentinel
• 从head.next开始依次向后循环，每一轮循环为了寻找current(即每一轮的head.next)的插入点，循环结束条件是head和head.next均存在
• 如果current.val大于head.val，则当前current位置正确无需移动，直接让head移动到下一位，
• 否则我们设置指针index指向sentinel.next，并且向后移动查找current的插入点，当index.next.val大于等于current.val时，index和index.next之间就是插入点，我们将current节点拼接在index和index.next之前。此时head（即current没有移动之前的前驱节点）后面的节点已经是原来head.next.next节点了，所以我们不需要移动head指针，继续判断即可

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const insertionSortList = (head) => {
	if (!head || !head.next) return head;
	let sentinel = new ListNode();
	sentinel.next = head;
	while (head && head.next) {
		let current = head.next;
		if (current.val >= head.val) {
			head = head.next;
		} else {
			let index = sentinel;
			while (index.next.val < current.val) {
				index = index.next;
			}
			head.next = head.next ? head.next.next : null;
			current.next = index.next;
			index.next = current;
		}
	}
	return sentinel.next;
};