C++實(shí)現(xiàn)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:
- Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list.
- 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.
- 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
鏈表的插入排序?qū)崿F(xiàn)原理很簡(jiǎn)單，就是一個(gè)元素一個(gè)元素的從原鏈表中取出來(lái)，然后按順序插入到新鏈表中，時(shí)間復(fù)雜度為 O(n2)，是一種效率并不是很高的算法，但是空間復(fù)雜度為 O(1)，以高時(shí)間復(fù)雜度換取了低空間復(fù)雜度，參見代碼如下：
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
類似題目：
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)
到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(147.鏈表插入排序)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)鏈表插入排序內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要給大家介紹了關(guān)于C 指針和OC 對(duì)象之間的轉(zhuǎn)換方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2018-03-03
C++入門之vector的底層實(shí)現(xiàn)詳解
這篇文章主要為大家介紹了C++入門之vector的底層實(shí)現(xiàn)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2021-11-11
這篇文章主要介紹了OpenCV 輪廓周圍繪制矩形框和圓形框,本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-01-01
在編程練習(xí)時(shí)我們經(jīng)常會(huì)遇到一些將一串亂序的數(shù)字排列成有序的數(shù)列(遞增,遞減)的問(wèn)題,以此起到解決問(wèn)題的效果,下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言中的5種簡(jiǎn)單排序算法的相關(guān)資料,需要的朋友可以參考下2023-03-03
C語(yǔ)言簡(jiǎn)明講解隊(duì)列的實(shí)現(xiàn)方法
隊(duì)列（Queue）與棧一樣，是一種線性存儲(chǔ)結(jié)構(gòu)，它具有如下特點(diǎn)：隊(duì)列中的數(shù)據(jù)元素遵循“先進(jìn)先出”（First?In?First?Out）的原則，簡(jiǎn)稱FIFO結(jié)構(gòu)。在隊(duì)尾添加元素，在隊(duì)頭刪除元素2022-04-04
C# 使用反射來(lái)實(shí)現(xiàn)對(duì)象的深度復(fù)制方法
下面小編就為大家?guī)?lái)一篇C# 使用反射來(lái)實(shí)現(xiàn)對(duì)象的深度復(fù)制方法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-01-01
C++實(shí)現(xiàn)LeetCode(162.求數(shù)組的局部峰值)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(162.求數(shù)組的局部峰值),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
用C語(yǔ)言實(shí)現(xiàn)單鏈表的各種操作(一)
本篇文章是對(duì)用C語(yǔ)言實(shí)現(xiàn)單鏈表的各種操作進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
下面小編就為大家?guī)?lái)一篇深入了解C++中map用法。小編覺得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨想過(guò)來(lái)看看吧2016-06-06
C語(yǔ)言學(xué)生信息管理系統(tǒng)小項(xiàng)目
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言學(xué)生信息管理系統(tǒng)小項(xiàng)目，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01