Sort a linked list using insertion sort.
[分析]
数组的插入排序通常做法是从当前元素往前遍历找到插入点,而单向链表无法回溯,于是每次从头开始寻找插入点。使用dummy额外节点技巧可使实现更简洁。
开始未将已排序部分和未排序部分分开,会死循环从而OutOfMemory,简单带入2->1 可看出bug。
public class Solution {
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode dummy = new ListNode(0);
ListNode prev = dummy;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
prev = dummy;
while (prev.next != null && prev.next.val <= curr.val)
prev = prev.next;
curr.next = prev.next;
prev.next = curr;
curr = next;
}
return dummy.next;
}
// Out of memory version
public ListNode insertionSortList(ListNode head) {
if (head == null || head.next == null)
return head;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode curr = head.next;
while (curr != null) {
ListNode next = curr.next;
prev = dummy;
while (prev.next != null && prev.next.val <= curr.val)
prev = prev.next;
curr.next = prev.next;
prev.next = curr;
curr = next;
}
return dummy.next;
}
}
分享到:
相关推荐
python python_leetcode题解之147_Insertion_Sort_List
- **插入排序(Insertion Sort)**: 构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 - **归并排序(Merge Sort)**: 采用分治法,将已有序的子序列合并,得到完全有序的序列。 - **...
copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归...
8. **Insertion sort list** (插入排序列表): 插入排序是基础排序算法之一,这里要求在链表上实现。在Java中,需要遍历链表并逐个插入新元素,保持已排序部分的有序性。 9. **Binary Tree Postorder Traversal** ...
Insertion Sort List 完成作业Quick sort Week6 10/11 国庆弹性放假 Week7 完成作业Heap sort Week8 完成作业Merge sort Week9 Week10 完成作业Binary Search Tree Week11 Week12 完成作业Hash table Week13 Week14 ...
lru缓存leetcode 力码 大批 152-最大乘积子阵列,169-多数元素,189-旋转阵列,198-房屋强盗 二分法 153-在旋转排序数组(II)中查找最小值,162-查找峰值元素 结构 155 分钟堆栈,173 二进制搜索树迭代器,HARD:...
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...
leetcode 答案 leetcode 08/18 Unique Paths 应该是简单的数学排列组合问题,提炼一下其实就一句话:有m个黑球,n个白球,有多少种不同的排列方式。...Insertion Sort List 在这里遇到前所未遇的惨败——提交了
第四、五周(InsertionSort、QuickSort) 第六周(Heap Sort) 第七周(Merge Sort) 第八周(Set Mismatch) 第九周(无新进度) 第十周(BST) 第十一周(Hash Table) 第十二、十三周(DFS(Stack) & BFS(Queue)) 第十四、十五周...
leetcode 答案About Me 我叫做林宏霖,绰号是呱呱。 我喜欢打排球,最喜欢的食物是芒果 我有一个很可爱的女友 Week1 中秋节放假 课程、分数说明 Week2 Linked List Linked list(连结串列)是一种常见的资料结构,其...
**1.12 Insertion Sort List (147)** - **问题描述**:对链表进行插入排序。 - **解题思路**: - 创建一个虚拟头节点,用于记录排序后的链表起始位置。 - 依次将原链表中的节点插入到已排序部分的适当位置。 **...
leetcode中文版 本教程是在下从零入门学算法的沉淀,希望能帮助到你~ :partying_face: PS: 在下还有一些其他的文章,欢迎关注~ 1. 基本概念 时间复杂度 空间复杂度 算法的特性和设计原则 2. 数据结构 栈(Stack) ...
leetcode切割分组 The algorithms implemented in Java Project Description sort the sort algorithm ds the data structure:stack/list/linked list/queue sort Name Time Complexity Space Complexity Stable ...
2. **排序算法**:快速排序(Quick Sort)、归并排序(Merge Sort)、堆排序(Heap Sort)和插入排序(Insertion Sort)等是常见的排序算法。在LeetCode上,你需要理解它们的工作原理,并能根据具体情况选择合适的...