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)原理很簡單，就是一個(gè)元素一個(gè)元素的從原鏈表中取出來，然后按順序插入到新鏈表中，時(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)文章
本文介紹了C語言中幾個(gè)常用的內(nèi)存函數(shù),包括memcpy、memmove、memset、memcmp的使用方法及其模擬實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2024-11-11
新手向超詳細(xì)的C語言實(shí)現(xiàn)動(dòng)態(tài)順序表
本文主要介紹了C語言實(shí)現(xiàn)動(dòng)態(tài)順序表，文中通過示例代碼介紹的非常詳細(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入門教程（二）：Node節(jié)點(diǎn)類
這篇文章主要介紹了Cocos2d-x 3.x入門教程（二）：Node節(jié)點(diǎn)類,本文對(duì)Node節(jié)點(diǎn)類做了一個(gè)簡明講解及Node類提供的函數(shù)做了說明,需要的朋友可以參考下2014-11-11
這篇文章主要為大家詳細(xì)介紹了C語言實(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)程問題有一定的幫助,需要的朋友可以參考下2014-07-07
C++?qsort函數(shù)排序與冒泡模擬實(shí)現(xiàn)流程詳解
qsort是一個(gè)庫函數(shù),基于快速排序算法實(shí)現(xiàn)的一個(gè)排序的函數(shù),下面這篇文章主要給大家介紹了關(guān)于C語言qsort()函數(shù)使用的相關(guān)資料,文中通過實(shí)例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-10-10
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xià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)方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04
google c++程序測試框架googletest使用教程詳解
​GoogleTest 是 Google 的 C++ 測試和模擬框架，可以幫助程序員測試C++程序的結(jié)果預(yù)期，這篇文章主要介紹了google c++程序測試框架googletest使用教程,需要的朋友可以參考下2021-08-08