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ù)雜度，參見(jiàn)代碼如下：
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)文章
本文介紹了C語(yǔ)言中幾個(gè)常用的內(nèi)存函數(shù),包括memcpy、memmove、memset、memcmp的使用方法及其模擬實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2024-11-11
新手向超詳細(xì)的C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)順序表
本文主要介紹了C語(yǔ)言實(shí)現(xiàn)動(dòng)態(tài)順序表，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-09-09
C++實(shí)現(xiàn)動(dòng)態(tài)數(shù)組功能
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)動(dòng)態(tài)數(shù)組功能，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-11-11
Cocos2d-x 3.x入門(mén)教程（二）：Node節(jié)點(diǎn)類
這篇文章主要介紹了Cocos2d-x 3.x入門(mén)教程（二）：Node節(jié)點(diǎn)類,本文對(duì)Node節(jié)點(diǎn)類做了一個(gè)簡(jiǎn)明講解及Node類提供的函數(shù)做了說(shuō)明,需要的朋友可以參考下2014-11-11
C語(yǔ)言實(shí)現(xiàn)掃雷游戲(含注釋詳解)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言實(shí)現(xiàn)掃雷游戲，含注釋，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-06-06
VC實(shí)現(xiàn)A進(jìn)程窗口嵌入到B進(jìn)程窗口中顯示的方法
這篇文章主要介紹了VC實(shí)現(xiàn)A進(jìn)程窗口嵌入到B進(jìn)程窗口中顯示的方法,對(duì)于理解windows程序運(yùn)行原理的進(jìn)程問(wèn)題有一定的幫助,需要的朋友可以參考下2014-07-07
C++?qsort函數(shù)排序與冒泡模擬實(shí)現(xiàn)流程詳解
qsort是一個(gè)庫(kù)函數(shù),基于快速排序算法實(shí)現(xiàn)的一個(gè)排序的函數(shù),下面這篇文章主要給大家介紹了關(guān)于C語(yǔ)言qsort()函數(shù)使用的相關(guān)資料,文中通過(guò)實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-10-10
C++實(shí)現(xiàn)簡(jiǎn)單走迷宮的代碼
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單走迷宮的代碼，利用回溯法求解，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-05-05
Qt一個(gè)進(jìn)程運(yùn)行另一個(gè)進(jìn)程的實(shí)現(xiàn)方法
本文主要介紹了Qt一個(gè)進(jìn)程運(yùn)行另一個(gè)進(jìn)程的實(shí)現(xiàn)方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04
google c++程序測(cè)試框架googletest使用教程詳解
​GoogleTest 是 Google 的 C++ 測(cè)試和模擬框架，可以幫助程序員測(cè)試C++程序的結(jié)果預(yù)期，這篇文章主要介紹了google c++程序測(cè)試框架googletest使用教程,需要的朋友可以參考下2021-08-08