冀教网 - 河北教师网站 - 专注于冀教版课本资源

 找回密码
 立即注册
搜索
热搜: 活动 交友 discuz
查看: 66|回复: 0

排序链表

[复制链接]

4万

主题

4万

帖子

12万

积分

管理员

Rank: 9Rank: 9Rank: 9

积分
124999
发表于 2020-5-23 18:59 | 显示全部楼层 |阅读模式
148. 排序链表

难度
O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
示例 1:
  1. 输入: 4->2->1->3输出: 1->2->3->4
复制代码
示例 2:
  1. 输入: -1->5->3->4->0输出: -1->0->3->4->5
复制代码
思路
\(O(nlogn)\)时间复杂度,分而治之,使用归并排序,数组归并排序代码可以看这里

  • 分割(找到中间节点,使用快慢指针)
  • 合并
coding
[code]# Definition for singly-linked list.# class ListNode:#     def __init__(self, x):#         self.val = x#         self.next = Noneclass Solution:    def sortList(self, head: ListNode) -> ListNode:        #递归退出条件        if not head or not head.next:            return head        #找到中间节点        mid = self.divide(head)        temp = mid.next        mid.next = None        #递归 合并        l = self.sortList(head)        r = self.sortList(temp)        return self.merge(l,r)            def divide(self,head):        #找到链表中间节点        if not head or not head.next:            return head        slow,fast = head,head.next.next        while fast and fast.next:            slow = slow.next            fast = fast.next.next        return slow        def merge(self,left,right):        #合并链表        new = ListNode(0)        curr = new        while left and right:            if left.val
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|冀教网 - 河北教师网站 - 专注于冀教版课本资源  

GMT+8, 2020-6-5 19:42 , Processed in 0.225169 second(s), 29 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表