Python LeetCode-148. 排序鏈表(難度-中等)(python)

1.題目

在 O(n log n) 時間復(fù)雜度和常數(shù)級空間復(fù)雜度下,對鏈表進(jìn)行排序痊剖。

示例 1:
輸入: 4->2->1->3
輸出: 1->2->3->4

示例 2:
輸入: -1->5->3->4->0
輸出: -1->0->3->4->5

2.分析

遞歸排序三部曲:1嘹狞,快慢指針找中點(diǎn)打厘;2望伦,遞歸調(diào)用mergeSort,3古程,合并兩個鏈表

3.解答

一種解答蔼卡,我還沒搞清楚,挣磨,雇逞,,

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def sortList(self, head):
        """
        主要是使用歸并的思路 先分再合
        :type head: ListNode
        :rtype: ListNode
        """
        if head is None:
            return None
        return self.minute(head)

    def minute(self, head):
        """
        這個方法主要是實(shí)現(xiàn)分的操作
        分的過程用快慢指針實(shí)現(xiàn)
        :param head:
        :return:
        """
        if head.next is None:
            return head
        quick, slow, temp = head, head, head
        while quick is not None and quick.next is not None:
            temp = slow
            slow = slow.next
            quick = quick.next.next
        temp.next = None  # 這一步就是將整個鏈表從中間分開 失去這一步 后面將無限循環(huán)

        i = self.minute(head)
        j = self.minute(slow)
        return self.Combined(i, j)

    def Combined(self, i, j):
        """
        這個方法主要實(shí)現(xiàn)合的操作
        合的過程就是從i 和 j開始比較 就是從開頭和中間開始比較 將兩個相比小的排在head后
        最后返回head即可
        :param i:ListNode
        :param j:ListNode
        :return:
        """
        TempNode = ListNode(0)
        temp = TempNode
        while i is not None and j is not None:
            if i.val <= j.val:
                temp.next = i
                i = i.next
            else:
                temp.next = j
                j = j.next
            temp = temp.next
        if i is not None:
            temp.next = i
        if j is not None:
            temp.next = j
        return TempNode.next
最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末茁裙,一起剝皮案震驚了整個濱河市塘砸,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌晤锥,老刑警劉巖谣蠢,帶你破解...
    沈念sama閱讀 222,681評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異查近,居然都是意外死亡,警方通過查閱死者的電腦和手機(jī)挤忙,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,205評論 3 399
  • 文/潘曉璐 我一進(jìn)店門霜威,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人册烈,你說我怎么就攤上這事戈泼。” “怎么了赏僧?”我有些...
    開封第一講書人閱讀 169,421評論 0 362
  • 文/不壞的土叔 我叫張陵大猛,是天一觀的道長。 經(jīng)常有香客問我淀零,道長挽绩,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,114評論 1 300
  • 正文 為了忘掉前任驾中,我火速辦了婚禮唉堪,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘肩民。我一直安慰自己唠亚,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,116評論 6 398
  • 文/花漫 我一把揭開白布持痰。 她就那樣靜靜地躺著灶搜,像睡著了一般。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上割卖,一...
    開封第一講書人閱讀 52,713評論 1 312
  • 那天前酿,我揣著相機(jī)與錄音,去河邊找鬼究珊。 笑死薪者,一個胖子當(dāng)著我的面吹牛,可吹牛的內(nèi)容都是我干的剿涮。 我是一名探鬼主播言津,決...
    沈念sama閱讀 41,170評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼取试!你這毒婦竟也來了悬槽?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 40,116評論 0 277
  • 序言:老撾萬榮一對情侶失蹤瞬浓,失蹤者是張志新(化名)和其女友劉穎初婆,沒想到半個月后,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體猿棉,經(jīng)...
    沈念sama閱讀 46,651評論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡磅叛,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,714評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了萨赁。 大學(xué)時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片弊琴。...
    茶點(diǎn)故事閱讀 40,865評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖杖爽,靈堂內(nèi)的尸體忽然破棺而出敲董,到底是詐尸還是另有隱情,我是刑警寧澤慰安,帶...
    沈念sama閱讀 36,527評論 5 351
  • 正文 年R本政府宣布腋寨,位于F島的核電站,受9級特大地震影響化焕,放射性物質(zhì)發(fā)生泄漏萄窜。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,211評論 3 336
  • 文/蒙蒙 一撒桨、第九天 我趴在偏房一處隱蔽的房頂上張望脂倦。 院中可真熱鬧,春花似錦元莫、人聲如沸赖阻。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,699評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽火欧。三九已至棋电,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間苇侵,已是汗流浹背赶盔。 一陣腳步聲響...
    開封第一講書人閱讀 33,814評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留榆浓,地道東北人于未。 一個月前我還...
    沈念sama閱讀 49,299評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像陡鹃,于是被迫代替她去往敵國和親烘浦。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,870評論 2 361

推薦閱讀更多精彩內(nèi)容

  • 概述 排序有內(nèi)部排序和外部排序萍鲸,內(nèi)部排序是數(shù)據(jù)記錄在內(nèi)存中進(jìn)行排序闷叉,而外部排序是因排序的數(shù)據(jù)很大,一次不能容納全部...
    蟻前閱讀 5,191評論 0 52
  • 1.插入排序—直接插入排序(Straight Insertion Sort) 基本思想: 將一個記錄插入到已排序好...
    依依玖玥閱讀 1,262評論 0 2
  • 一些概念 數(shù)據(jù)結(jié)構(gòu)就是研究數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)以及它們之間相互關(guān)系脊阴,并對這種結(jié)構(gòu)定義相應(yīng)的運(yùn)算握侧,而且確保經(jīng)過這...
    Winterfell_Z閱讀 5,854評論 0 13
  • 1.重復(fù)字符可以用來限制輸入的類型,以及輸入的位數(shù): 2.基本重復(fù)描述字符如下:
    不過一書生閱讀 332評論 0 0
  • 橫著看:體現(xiàn)了音形對應(yīng)的思想嘿期,訓(xùn)練眼睛“分切關(guān)”品擎,訓(xùn)練耳朵“重音漂移不發(fā)音”。大寫“分切關(guān)”备徐,因?yàn)橐曈X記憶對記憶的...
    Tyger老師閱讀 1,326評論 0 6