147. 对链表进行插入排序

🟠   🔖  链表 排序  🔗 力扣 LeetCode

题目

Given the head of a singly linked list, sort the list using insertion sort , and return the sorted list 's head.

The steps of the insertion sort algorithm:

1. Insertion sort iterates, consuming one input element each repetition and growing a sorted output list.
2. 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.
3. It repeats until no input elements remain.

The following is a graphical example of the insertion sort algorithm. The partially sorted list (black) initially contains only the first element in the list. One element (red) is removed from the input data and inserted in-place into the sorted list with each iteration.


Example 1:

Input: head = [4,2,1,3]

Output: [1,2,3,4]

Example 2:

Input: head = [-1,5,3,4,0]

Output: [-1,0,3,4,5]

Constraints:

• The number of nodes in the list is in the range [1, 5000].
• -5000 <= Node.val <= 5000

题目大意

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

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

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。


对链表进行插入排序。

解题思路

1. 首先，我们需要创建一个虚拟头节点 res，并将其指向链表的头部。这样做是为了方便在头部插入节点。

2. 然后，我们遍历链表中的每个节点，将其插入已排序的链表中。初始时，已排序的链表只包含虚拟头节点。

3. 在遍历的过程中，我们将当前节点与已排序链表中的节点进行比较。找到合适的位置后，将当前节点插入到已排序链表中。

4. 插入操作需要先找到插入的位置，然后进行节点的插入。注意在找到插入位置前，要一直移动指针。

5. 最后，返回虚拟头节点的下一个节点，即排序后的链表头。

虽然插入排序不如一些高级排序算法的时间复杂度低，但在链表这样的数据结构上，插入排序是一种简单且有效的排序算法。

复杂度分析

• 时间复杂度：O(n^2)，其中 n 是链表的长度。
• 空间复杂度：O(1)，使用了常数级别的额外空间。

代码

/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var insertionSortList = function (head) {
	let res = new ListNode(0);
	let cur = head;
	while (cur) {
		let next = cur.next;
		let prev = res;
		while (prev.next && prev.next.val < cur.val) {
			prev = prev.next;
		}
		cur.next = prev.next;
		prev.next = cur;
		cur = next;
	}
	return res.next;
};

相关题目

题号	标题	题解	标签	难度
148	排序链表	[✓]	链表 双指针 分治 2+
708	循环有序列表的插入 🔒		链表