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;
}
}
分享到:
相关推荐
copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归...
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 ...
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
lru缓存leetcode 力码 大批 152-最大乘积子阵列,169-多数元素,189-旋转阵列,198-房屋强盗 二分法 153-在旋转排序数组(II)中查找最小值,162-查找峰值元素 结构 155 分钟堆栈,173 二进制搜索树迭代器,HARD:...
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(连结串列)是一种常见的资料结构,其...
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 ...
Insertion Sort List 归并排序 Merge Two Sorted Arrays Merge Two Sorted Lists Merge k Sorted Lists Sort List 快速排序 Sort Colors Kth Largest Element in an Array 桶排序 First Missing Positive 计数排序 H...