148.排序链表

ゞ浴缸里的玫瑰 2023-08-17 16:56 157阅读 0赞

多次调用递归函数，排序左右函数，快慢指针切片成左右函数，还有一个运用俩个函数的函数。反正写在代码里了，应该能看懂

class Solution:
        def sortList(self, head: ListNode) -> ListNode:
            def cut(head):
                s,f = head,head.next
                while f and f.next:
                    s = s.next
                    f = f.next.next
                right = s.next
                s.next = None
                return head,right
            #快慢指针，昨天的题也有用快慢指针的思路，把一个链表断开
            def min_(l,r):
                if not l:
                    return r
                if not r:
                    return l#去除NULL
                if l.val<r.val:
                    l.next = min_(l.next,r)
                    return l
                r.next = min_(l,r.next)
                return r 
            #排序这做链表和右边链表
            def Sort(head):
                if not head or not head.next:
                    return head
                left,right = cut(head)
                l = Sort(left)
                r = Sort(right)#这个我不懂，一开始用return min_(left,right),后来发现只断了一次链表，没法排，才递归出半链表的排序
                return min_(l,r)     
            return Sort(head)

发表评论取消回复

表情：

评论列表（有 0 条评论，157人围观）

还没有评论，来说两句吧...

相关阅读

相关 148. 排序链表

§ 解答一：归并排序（递归法） * 题目要求时间空间复杂度分别为O(nlogn)O(nlogn)O(nlogn)和O(1)O(1)O(1)，根据时间复杂度我们自然...

刺骨的言语ヽ痛彻心扉/ 2024年04月17日 19:42/ 0 赞/ 69 阅读

相关 148.排序链表

多次调用递归函数，排序左右函数，快慢指针切片成左右函数，还有一个运用俩个函数的函数。反正写在代码里了，应该能看懂 class Solution: de

ゞ浴缸里的玫瑰/ 2023年08月17日 16:56/ 0 赞/ 158 阅读

相关 148. 排序链表

题目： [148. 排序链表][148.] ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_tex

女爷i/ 2023年02月21日 14:24/ 0 赞/ 8 阅读

相关 148. 排序链表

题目来源 [148. 排序链表][148.] 题目描述 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shado

朱雀/ 2023年02月20日 13:32/ 0 赞/ 191 阅读

相关 148排序链表

一、前言标签：归并排序。问题来源LeetCode 148 难度：中等。问题链接：[https://leetcode-cn.com/problems/sort-l

以你之姓@/ 2023年02月08日 15:53/ 0 赞/ 22 阅读

相关 LeetCode148--排序链表

题目分析时间复杂度限制下，符合要求的常规排序算法可以用快速，归并.....来完成，这里使用的是归并排序，归并排序最重要的的就是合并操作了，而且他合并的是两个有序集，对于

古城微笑少年丶/ 2023年01月16日 14:28/ 0 赞/ 189 阅读

相关 leetcode148.排序链表

对链表进行归并排序原题目链接 [排序链表][Link 1] 本题目要求时间复杂度为O(`n`log`n`)因此不难想到使用归并排序,而对与链表的归并排序来说,比较核

淡淡的烟草味﹌/ 2022年12月23日 03:23/ 0 赞/ 193 阅读

相关 148. 排序链表

> 给你链表的头结点 head ，请将其按升序排列并返回排序后的链表。 > > ![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow

女爷i/ 2022年10月10日 09:42/ 0 赞/ 234 阅读

相关 LeetCode148.链表排序

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

以你之姓@/ 2022年02月13日 05:09/ 0 赞/ 246 阅读

相关 LeetCode148. 排序链表

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。示例 1: 输入: 4->2->1->3 输出: 1->2->3->4 示例 2: 输

╰半橙微兮°/ 2021年09月27日 00:20/ 0 赞/ 342 阅读