`

Leetcode - Insertion Sort List

 
阅读更多
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-leetcode题解之147-Insertion-Sort-List

    python python_leetcode题解之147_Insertion_Sort_List

    算法-leetcode-剑指offer上的题很多

    - **插入排序(Insertion Sort)**: 构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。 - **归并排序(Merge Sort)**: 采用分治法,将已有序的子序列合并,得到完全有序的序列。 - **...

    gasstationleetcode-leetcode-in-niuke:在牛客网上的在线编程中的leetcode在线编程题解

    copy-list-with-random-pointer 复杂度 single-number 动态规划 candy 贪心 gas-station 动态规划 palindrome-partitioning-ii 动态规划 triangle 树 sum-root-to-leaf-numbers 动态规划 distinct-subsequences 递归...

    leetcode-answer-and-analysis(part).zip_图形图像处理_Java_

    8. **Insertion sort list** (插入排序列表): 插入排序是基础排序算法之一,这里要求在链表上实现。在Java中,需要遍历链表并逐个插入新元素,保持已排序部分的有序性。 9. **Binary Tree Postorder Traversal** ...

    看leetcode吃力-my-learning-note:大三下学期之资料结构与演算法课程内容与练习

    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 ...

    lrucacheleetcode-leetcode:leetcode

    lru缓存leetcode 力码 大批 152-最大乘积子阵列,169-多数元素,189-旋转阵列,198-房屋强盗 二分法 153-在旋转排序数组(II)中查找最小值,162-查找峰值元素 结构 155 分钟堆栈,173 二进制搜索树迭代器,HARD:...

    LeetCode最全代码

    * [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...

    LeetCode:LeetCode解决方案

    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:leetcode

    leetcode 答案 leetcode 08/18 Unique Paths 应该是简单的数学排列组合问题,提炼一下其实就一句话:有m个黑球,n个白球,有多少种不同的排列方式。...Insertion Sort List 在这里遇到前所未遇的惨败——提交了

    leetcode530-my-learning-note:我的学习笔记

    第四、五周(InsertionSort、QuickSort) 第六周(Heap Sort) 第七周(Merge Sort) 第八周(Set Mismatch) 第九周(无新进度) 第十周(BST) 第十一周(Hash Table) 第十二、十三周(DFS(Stack) & BFS(Queue)) 第十四、十五周...

    leetcode答案-python:Python

    leetcode 答案About Me 我叫做林宏霖,绰号是呱呱。 我喜欢打排球,最喜欢的食物是芒果 我有一个很可爱的女友 Week1 中秋节放假 课程、分数说明 Week2 Linked List Linked list(连结串列)是一种常见的资料结构,其...

    Leetcode答案(c++版)

    **1.12 Insertion Sort List (147)** - **问题描述**:对链表进行插入排序。 - **解题思路**: - 创建一个虚拟头节点,用于记录排序后的链表起始位置。 - 依次将原链表中的节点插入到已排序部分的适当位置。 **...

    leetcode中文版-ts-datastructures-algorithms:和我一起学算法吧!

    leetcode中文版 本教程是在下从零入门学算法的沉淀,希望能帮助到你~ :partying_face: PS: 在下还有一些其他的文章,欢迎关注~ 1. 基本概念 时间复杂度 空间复杂度 算法的特性和设计原则 2. 数据结构 栈(Stack) ...

    leetcode切割分组-algorithm-java:Java实现的算法

    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

    2. **排序算法**:快速排序(Quick Sort)、归并排序(Merge Sort)、堆排序(Heap Sort)和插入排序(Insertion Sort)等是常见的排序算法。在LeetCode上,你需要理解它们的工作原理,并能根据具体情况选择合适的...

Global site tag (gtag.js) - Google Analytics