首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

链表合并排序的实现

链表合并排序是一种常见的排序算法,用于将多个有序链表合并为一个有序链表。下面是链表合并排序的实现步骤:

  1. 定义一个辅助函数merge,用于合并两个有序链表。它的输入是两个链表的头节点,输出是合并后的有序链表的头节点。
  2. 在主函数中,先判断输入的链表是否为空,若为空则直接返回空链表。
  3. 若链表不为空,递归地将链表一分为二,分别对左右两部分链表进行排序。
  4. 最后,调用merge函数将排好序的左右两部分链表合并成一个有序链表,并返回合并后的链表的头节点。

下面是代码示例:

代码语言:txt
复制
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def merge(left, right):
    dummy = ListNode(0)  # 创建一个哑节点作为合并后链表的头节点
    cur = dummy  # 创建一个指针指向当前节点
    while left and right:
        if left.val < right.val:
            cur.next = left
            left = left.next
        else:
            cur.next = right
            right = right.next
        cur = cur.next
    if left:
        cur.next = left
    if right:
        cur.next = right
    return dummy.next

def merge_sort(head):
    if not head or not head.next:
        return head
    
    slow = head
    fast = head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    right = merge_sort(slow.next)  # 递归排序右半部分链表
    slow.next = None  # 断开链表,将链表一分为二
    left = merge_sort(head)  # 递归排序左半部分链表

    return merge(left, right)  # 合并左右两部分链表

# 测试用例
# 创建链表1->4->3->2->5
head = ListNode(1)
head.next = ListNode(4)
head.next.next = ListNode(3)
head.next.next.next = ListNode(2)
head.next.next.next.next = ListNode(5)

# 对链表进行合并排序
sorted_head = merge_sort(head)

# 输出排序后的链表
while sorted_head:
    print(sorted_head.val, end=" ")
    sorted_head = sorted_head.next

链表合并排序的时间复杂度为O(nlogn),其中n是链表的总节点数。该算法适用于多个有序链表的合并排序,例如合并k个有序链表可以通过多次合并两个有序链表的方式实现。对于大规模数据的排序,链表合并排序具有较好的性能表现。

腾讯云提供了云计算相关的产品和服务,可以通过以下链接了解更多信息:

  • 腾讯云云服务器CVM:提供灵活可扩展的云服务器实例,适用于各种计算场景。
  • 腾讯云云数据库MySQL版:提供高性能、高可用的关系型数据库服务,适用于存储和管理数据。
  • 腾讯云CDN:提供全球加速、缓存分发的内容分发网络服务,加速网站和应用的访问速度。
  • 腾讯云人工智能:提供各类人工智能算法和工具,帮助开发者构建智能应用。
  • 腾讯云区块链服务:提供快速构建和部署区块链网络的服务,支持多种区块链框架。

希望以上信息能对你有所帮助!

页面内容是否对你有帮助?
有帮助
没帮助

相关·内容

3分32秒

【剑指Offer】25. 合并两个排序的链表

288
43分29秒

Golang教程 数据结构和设计模式 38 链表冒泡排序与选择排序 学习猿地

1分34秒

Python实现多Excel多Sheet批量合并

9分5秒

109 指针实现冒泡排序

21分49秒

18-尚硅谷-Scala数据结构和算法-双向链表的实现

1分54秒

C语言实现冒泡排序

17分11秒

Golang教程 数据结构和设计模式 41 快速排序链表 学习猿地

3分59秒

12,双向链表插入新节点,代码该如何实现?

21分38秒

Golang教程 数据结构和设计模式 39 插入排序链表 学习猿地

13分15秒

Golang教程 数据结构和设计模式 40 归并排序链表 学习猿地

17分58秒

164_尚硅谷_Go核心编程_冒泡排序的实现.avi

12分17秒

113 - 尚硅谷 - SparkCore - 案例实操 - 需求一 - 功能实现 - 合并点击,下单,支付的数量

领券