[LeetCode] 147. Insertion Sort List 链表插入排序
2023-09-11 14:21:39 时间
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
链表的插入排序实现原理很简单,就是一个元素一个元素的从原链表中取出来,然后按顺序插入到新链表中,时间复杂度为 O(n2),是一种效率并不是很高的算法,但是空间复杂度为 O(1),以高时间复杂度换取了低空间复杂度,参见代码如下:
class Solution { public: ListNode* insertionSortList(ListNode* head) { ListNode *dummy = new ListNode(-1), *cur = dummy; while (head) { ListNode *t = head->next; cur = dummy; while (cur->next && cur->next->val <= head->val) { cur = cur->next; } head->next = cur->next; cur->next = head; head = t; } return dummy->next; } };
Github 同步地址:
https://github.com/grandyang/leetcode/issues/147
类似题目:
Insert into a Cyclic Sorted List
参考资料:
https://leetcode.com/problems/insertion-sort-list/
https://leetcode.com/problems/insertion-sort-list/discuss/46423/Explained-C%2B%2B-solution-(24ms)
相关文章
- Java实现 LeetCode 810 黑板异或游戏 (分析)
- Java实现 LeetCode 561 数组拆分 I(通过排序算法改写PS:难搞)
- Java实现 LeetCode 540 有序数组中的单一元素(位运算入门)
- Java实现 LeetCode 114 二叉树展开为链表
- Java实现LeetCode #986 - Interval List Intersections
- (LeetCode 92)Reverse Linked List II
- (LeetCode 86)Partition List
- [LeetCode] Flatten Nested List Iterator
- [LeetCode] Insertion Sort List
- LeetCode(68):文本左右对齐
- LeetCode-522. 最长特殊序列 II【双指针】
- leetcode算法第8题
- 【LeetCode Python实现】9. 回文数(简单):=海象运算符的使用
- [LeetCode] 206. Reverse Linked List ☆(反转链表)
- [LeetCode] 83. Remove Duplicates from Sorted List ☆(从有序链表中删除重复项)
- 【LeetCode】Partition List
- Leetcode - Insertion Sort List
- 【Leetcode】Partition List (Swap)
- [LeetCode] Linked List Cycle II
- leetcode——Insertion Sort List 对链表进行插入排序(AC)
- leetcode - Convert Sorted List to Binary Search Tree
- leetcode 110. Balanced Binary Tree
- 【Leetcode刷题Python】从列表list中创建一颗二叉树