C++实现LeetCode(147.链表插入排序)

[LeetCode] 147. Insertion Sort List 链表插入排序

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:

  1. Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
  2. 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.
  3. 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

类似题目：

Sort List

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)

https://leetcode.com/problems/insertion-sort-list/discuss/46420/An-easy-and-clear-way-to-sort-(-O(1)-space-)

到此这篇关于C++实现LeetCode(147.链表插入排序)的文章就介绍到这了,更多相关C++实现链表插入排序内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • C++实现LeetCode(200.岛屿的数量)

    [LeetCode] 200. Number of Islands 岛屿的数量 Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four

  • C++实现LeetCode(140.拆分词句之二)

    [LeetCode] 140.Word Break II 拆分词句之二 Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, add spaces in s to construct a sentence where each word is a valid dictionary word. Return all such possible sentences. Not

  • C++实现LeetCode(146.近最少使用页面置换缓存器)

    [LeetCode] 146. LRU Cache 最近最少使用页面置换缓存器 Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exist

  • C++实现LeetCode(138.拷贝带有随机指针的链表)

    C++实现LeetCode(138.拷贝带有随机指针的链表)

    [LeetCode] 138. Copy List with Random Pointer 拷贝带有随机指针的链表 A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list. Example 1: Input: {"$id"

  • C++实现LeetCode(134.加油站问题)

    [LeetCode] 134.Gas Station 加油站问题 There are N gas stations along a circular route, where the amount of gas at station i is gas[i]. You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1)

  • C++实现LeetCode(135.分糖果问题)

    [LeetCode] 135.Candy 分糖果问题 There are N children standing in a line. Each child is assigned a rating value. You are giving candies to these children subjected to the following requirements: Each child must have at least one candy. Children with a high

  • C++实现LeetCode(133.克隆无向图)

    C++实现LeetCode(133.克隆无向图)

    [LeetCode] 133. Clone Graph 克隆无向图 Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors. Example: Input: {"$id":

  • C++验证LeetCode包围区域的DFS方法

    验证LeetCode Surrounded Regions 包围区域的DFS方法 在LeetCode中的Surrounded Regions 包围区域这道题中,我们发现用DFS方法中的最后一个条件必须是j > 1,如下面的红色字体所示,如果写成j > 0的话无法通过OJ,一直百思不得其解其中的原因,直到有网友告诉我说他验证了最后一个大集合在本地机子上可以通过,那么我也来验证看看吧. class Solution { public: void solve(vector<vector<

  • C++实现LeetCode(147.链表插入排序)

    C++实现LeetCode(147.链表插入排序)

    [LeetCode] 147. Insertion Sort List 链表插入排序 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

  • C++实现LeetCode(148.链表排序)

    [LeetCode] 148. Sort List 链表排序 Sort a linked list in O(n log n) time using constant space complexity. 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 常见排序方法有

  • javascript数据结构之双链表插入排序实例详解

    本文实例讲述了javascript数据结构之双链表插入排序实现方法.分享给大家供大家参考,具体如下: 数组存储前提下,插入排序算法,在最坏情况下,前面的元素需要不断向后移,以便在插入点留出空位,让目标元素插入. 换成链表时,显然无需做这种大量移动,根据每个节点的前驱节点"指针",向前找到插入点后,直接把目标值从原链表上摘下,然后在插入点把链表断成二截,然后跟目标点重新接起来即可. <!doctype html> <html> <head> <t

  • JavaScript实现链表插入排序和链表归并排序

    本篇文章详细的介绍了JavaScript实现链表插入排序和链表归并排序,链表的归并排序就是对每个部分都进行归并排序,然后合并在一起. 1.链表 1.1链表的存储表示 //链表的存储表示 typedef int ElemType; typedef struct LNode { ElemType data; struct LNode *next; }LNode, *LinkList; 1.2基本操作 创建链表: /* * 创建链表. * 形参num为链表的长度,函数返回链表的头指针. */ Link

  • C++实现LeetCode(倒置链表之二)

    [LeetCode] 92. Reverse Linked List II 倒置链表之二 Reverse a linked list from position m to n. Do it in one-pass. Note: 1 ≤ m ≤ n ≤ length of list. Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL 很奇怪为何

  • C++实现LeetCode(倒置链表)

    [LeetCode] Reverse Linked List 倒置链表 Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up: A linked list can be reversed either iteratively or recursively. Could you implement

  • C++实现LeetCode(143.链表重排序)

    [LeetCode] 143.Reorder List 链表重排序 Given a singly linked list L: L0→L1→-→Ln-1→Ln, reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→- You may not modify the values in the list's nodes, only nodes itself may be changed. Example 1: Given 1->2->3->4, reorder it t

  • Leetcode常见链表问题及代码示例

    按规定区间反转链表 思路:可以考虑成一种把前后数字的结点断开重新组合的问题 /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* reverseBetween(ListNode* head, int m,

  • Java数据结构和算法之冒泡,选择和插入排序算法

    Java数据结构和算法之冒泡,选择和插入排序算法

    目录 1.冒泡排序 2.选择排序 3.插入排序 4.总结 1.冒泡排序 这个名词的由来很好理解,一般河水中的冒泡,水底刚冒出来的时候是比较小的,随着慢慢向水面浮起会逐渐增大,这物理规律我不作过多解释,大家只需要了解即可. 冒泡算法的运作规律如下: ①.比较相邻的元素.如果第一个比第二个大,就交换他们两个. ②.对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.这步做完后,最后的元素会是最大的数(也就是第一波冒泡完成). ③.针对所有的元素重复以上的步骤,除了最后一个. ④.持续每次对越

  • C语言深入讲解链表的使用

    C语言深入讲解链表的使用

    目录 一.链表的概念 二.链表的分类 1. 单向或者双向链表 2. 带头或者不带头(是否有自带哨兵位头结点) 3. 循环或者非循环链表 4. 无头单向非循环链表和带头双向循环链表 3.链表的实现(代码和注释) 4.链表oj题(小试牛刀) 总结 现实生活中的火车就像一个完整的链表,现在我们来深入理解一下链表这个数据结构. 一.链表的概念 概念:链表是一种物理存储结构上非连续.非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链 接次序实现的 . 注: 1.从上图中可看出,链式结构在逻辑上是连续

随机推荐