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