问题描述:
Sort a linked list using insertion sort.
原问题链接:https://leetcode.com/problems/insertion-sort-list/
问题分析
这里因为是针对链表进行插入排序,其过程和普通数组的插入排序有点不一样。相对来说因为没有直接的索引访问,它要复杂不少。在针对链表的插入排序实现前,我们先看看基于数组的插入排序过程。对于数组的插入排序,它是从索引为1的元素开始,每次和它前面的元素比较,碰到一个比当前大的元素,就和这个元素换个位置,一直到它之前的元素比它小。
在上面的过程,这是针对可以很方便的前后向访问的过程。但是对于链表来说,从后往前则比较麻烦。那么我们可以这么来考虑,首先建立一个空的链表,然后从原来的链表里每次去一个元素加入到这个新链表中。针对第一个元素来说,只是把原来的第一个元素挪到新链表里就可以了。对于后面的元素,我们每次都在新链表里判断这个元素所在的位置,然后将这个元素加入到指定的位置就可以了。我们每次要记录保存原来链表里下一个元素的位置。同时,为了方便这个新链表的访问,我们可以建立一个临时的节点,每次加元素的时候就在这个节点的后面加。
这样,我们只要保证原来链表最终的节点为空就可以了。详细的代码实现如下:
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode insertionSortList(ListNode head) { if(head == null || head.next == null) return head; ListNode dummy = new ListNode(0); ListNode pre = dummy; ListNode cur = head; while(cur != null) { ListNode next = cur.next; pre = dummy; while(pre.next != null && pre.next.val <= cur.val) { pre = pre.next; } cur.next = pre.next; pre.next = cur; cur = next; } return dummy.next; } }
相关推荐
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 在这里遇到前所未遇的惨败——提交了
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
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 ...
leetcode 答案About Me 我叫做林宏霖,绰号是呱呱。 我喜欢打排球,最喜欢的食物是芒果 我有一个很可爱的女友 Week1 中秋节放假 课程、分数说明 Week2 Linked List Linked list(连结串列)是一种常见的资料结构,其...
insertion-sort-list 树 binary-tree-postorder-traversal 树 binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态...
第四、五周(InsertionSort、QuickSort) 第六周(Heap Sort) 第七周(Merge Sort) 第八周(Set Mismatch) 第九周(无新进度) 第十周(BST) 第十一周(Hash Table) 第十二、十三周(DFS(Stack) & BFS(Queue)) 第十四、十五周...
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 ...
leetcode中文版 本教程是在下从零入门学算法的沉淀,希望能帮助到你~ :partying_face: PS: 在下还有一些其他的文章,欢迎关注~ 1. 基本概念 时间复杂度 空间复杂度 算法的特性和设计原则 2. 数据结构 栈(Stack) ...
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...