溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

C++怎么實(shí)現(xiàn)鏈表插入排序

發(fā)布時(shí)間：2021-07-28 19:12:36 來源：億速云 閱讀：254 作者：chen 欄目：開發(fā)技術(shù)

本篇內(nèi)容主要講解“C++怎么實(shí)現(xiàn)鏈表插入排序”，感興趣的朋友不妨來看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“C++怎么實(shí)現(xiàn)鏈表插入排序”吧!

鏈表插入排序

鏈表的插入排序?qū)崿F(xiàn)原理很簡(jiǎ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;
    }
};

到此，相信大家對(duì)“C++怎么實(shí)現(xiàn)鏈表插入排序”有了更深的了解，不妨來實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！

向AI問一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

c++
AI
助
手