开发者社区

文档建议反馈控制台

最新优惠活动

文章/答案/技术大牛

发布

链表的Mergesort的Python实现不起作用

链表的Mergesort是一种常用的排序算法，用于对链表进行排序。下面是链表的Mergesort的Python实现：

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

def mergeSort(head):
    if not head or not head.next:
        return head
    
    # 找到链表的中点
    slow, fast = head, head.next
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    
    # 将链表分为两部分
    mid = slow.next
    slow.next = None
    
    # 递归地对两部分链表进行排序
    left = mergeSort(head)
    right = mergeSort(mid)
    
    # 合并两个有序链表
    dummy = ListNode(0)
    curr = dummy
    while left and right:
        if left.val < right.val:
            curr.next = left
            left = left.next
        else:
            curr.next = right
            right = right.next
        curr = curr.next
    
    curr.next = left if left else right
    
    return dummy.next

这段代码实现了链表的Mergesort算法。具体步骤如下：

定义一个ListNode类，表示链表的节点。
定义mergeSort函数，用于对链表进行排序。如果链表为空或只有一个节点，直接返回链表。
使用快慢指针找到链表的中点，将链表分为两部分。
递归地对两部分链表进行排序。
合并两个有序链表，创建一个虚拟头节点dummy和一个当前节点curr。
比较左右两个链表的节点值，将较小的节点连接到curr的后面。
更新curr和被选中节点的指针。
如果左链表还有剩余节点，将剩余节点连接到curr的后面。
如果右链表还有剩余节点，将剩余节点连接到curr的后面。
返回合并后的链表。

链表的Mergesort算法的优势在于它的时间复杂度为O(nlogn)，且不需要额外的空间。它适用于对链表进行排序的场景。

腾讯云提供了多种云计算相关产品，包括云服务器、云数据库、云存储等。具体推荐的产品和产品介绍链接地址可以参考腾讯云官方文档：腾讯云产品。

页面内容是否对你有帮助？

有帮助

没帮助

相关·内容

python单链表的实现

''' 当加入第一个node节点的时候,会有几个值,(这里的self.tail.next 其实就是node.next) head = item = tail = Node(object element1...init__(self): self.head= None self.tail = None def append(self,value): #添加链表前需要...,实例化一个节点,来进行赋值 node = Node(value) #实例化节点 #添加链表,首先判断链表是否为空, # 空列表时 head= tail...if self.head == None: self.head = node # self.tail = node #当链表不为空时向后添加...append的改变而改变了,只是再重新赋值之后才会改变的 # self.tail = node #现在的结尾部分被重新赋值 else: self.tail.next

4793 0

Python实现链表

单链表： # -*- coding:utf-8 -*- class Node(object): """节点""" def __init__(self,elem): self.elem...= elem self.next = None class SingleLinkList(object): """单链表""" #头结点 def __init..._head = node def append(self,item): """链表尾部添加元素,叫尾插法""" node = Node(item)...node.next = pre.next pre.next = node def remove(self,item): """删除指定的节点...cur.prev.next = node cur.prev = node def remove(self,item): """删除指定的节点

6181 0

python 实现线性链表（单链表）

初学python，拿数据结构中的线性链表存储结构练练手，理论比较简单，直接上代码。 #!.../usr/bin/python # -*- coding:utf-8 -*- # Author: Hui # Date: 2017-10-13 # 结点类， class Node: def...数据域 self.next = None # 指针域 def get_data(self): return self.data # 链表类...return self.get_len() == 0 def get_len(self): # 返回链表长度 length = 0...：\t', list.print_list(head) print '链表是否空：\t', list.is_empty() print '链表长度：\t', list.get_len

6513 0

链表的实现

链表之前我们已经介绍过，这章笔记我们就来通过C++语言实现一个简单的链表 C语言表示链表的一个节点 struct Node { int data; struct Node*link; } 上图: 头节点...首先链表有一个头节点，他没有数据，类型是节点指针他负责标识这个链表，比如我现在这个头节点叫head ，如果head = NULL表示链表为空如果head不为空则表示链表有节点。...通过malloc给节点在堆上分配内存 Node*temp = malloc(sizeof(Node)); 然后通过头节点指向这个节点 head = temp; 这样我们就创建了一个有节点的链表我们想在已有的节点后面再创建一个节点该如何创建呢...=NULL) { temp = temp->link; } printf("the last data of Node is %d",temp->data); 很简单的逻辑头节点是不可以被修改的，因为头结点是链表的标识...，如果修改掉链表标识，链表将无法成立

1391 0

Python实现单链表

class Node: '''节点结构''' def __init__(self, data, nextNode=None): #设置当前节点的值和指向下一个节点的指针 self.data...self.next self.next = node #头节点 head = Node(0) p = head for i in range(1, 10): #依次生成10个数字，并创建相应的节点...#把节点连接到链表的尾部 n = Node(i) p.next = n p = n p = head #遍历链表节点，在值为3的节点后面插入值为3.5的新节点 while True...: if p.data == 3: p.insertAfter(Node(3.5)) break else: p = p.next p = head #遍历链表并输出每个节点的值

8415 0

python实现单链表

8 import sys class Lnode(): def __init__(self,elem,next=None): self.elem = elem #节点的值...self): L = Lnode(None,None) self.head = L #定义头节点 self.length = 0 #链表元素个数... # 链表是否为空 def isempty(self): if self.head.next is None: return True ...newNode.next = self.head.next self.head.next = newNode self.length += 1 #在指定元素的位置后面插入... sys.stdout.write("%s " %(p.elem)) print return #查找元素，返回指向该元素的节点

4673 0

用Python实现链表---单向循环链表

1 问题如何利用python实现单向循环链表简化数学问题？...2 方法 add方法：向链表头部添加一个节点data append方法：向链表尾部添加一个节点，值为data remove方法：删除链表中第一个值为data的节点代码清单 1 class Node:...nodes_list()) l1.modify(1, 3) print(l1.nodes_list()) print("查找") print(l1.search(3)) 3 结语运用单向循环链表可以用来解决约瑟夫环问题...，但目前通过python来解决此类问题只能停留在最基本的层面上，要想深入解决此类问题，则要通过后续的学习，了解更多的python知识，从来实现对该类问题的完美解决。

1573 0

链表的实现

链表分为单向链表、双向链表和循环链表。链表这种数据结构就像是火车车厢一样，每个车厢可以插入到任意的的位置。...isEmpty(): 如果链表中不包含任何元素，返回 true，如果链表长度大于 0 则返回 false。下面来一一进行实现。...先实现单向链表（上一个数据的指针指向下一个数据的存储地址），然后在这基础上实现双向链表和循环链表。这里使用 ES6 class 的形式来实现。...remove 方法可以结合 indexOf 方法和 removeAt 方法来实现。先通过 indexOf方法获取要删除元素的索引，然后通过索引去删除指定的元素。...false : this.removeAt(idx); } insert(index,elem) 方法这个方法跟删除一个元素的实现思路很相似，也需要条件判断，也需要断开链表然后插入新的内容。

5301 0

链表的实现

#include<iostream> #include<stdlib.h> using namespace std; typedef int ElemType;...

6035 0

链表和双向链表的实现

前言 ---- 链表中的数据通过指针连接，添加、插入或删除节点只需要修改指针指向实现思路实现一个链表需要具备以下方法在链表尾部添加节点获取链表所有节点的数据链表指定位置插入元素获取链表指定位置的节点数据...获取节点在链表中的位置更新链表指定位置的数据移除链表指定位置的节点移除链表中的指定节点判断链表是否为空获取链表长度链表内部需要定义head指针和链表长度实现代码定义head指针和length...(linkedList.size()) 双向链表双向链表的指针是双向的，前指针指向上一个节点，后指针指向下一个节点 head指向第一个节点,tail指向最后一个节点双向链表实现思路需要具备以下方法...尾部插入元素任意位置插入元素获取所有节点数据正向遍历链表获取节点数据反向遍历链表获取节点数据获取指定位置的节点数据获取指定数据在链表中的位置更新指定位置的节点数据移除指定位置的节点移除指定数据的节点...判断链表是否为空获取链表长度定义head和tail分别指向第一个节点和最后一个节点代码实现 /** * 双向链表 */ function DoublyLinkedList() { //指向第一个节点

7054 0

Python 实现单向链表

单向链表 #!...usr/bin/env python # -*- coding:utf-8 -*- """ @author:yzk13 @time: 2018/04/15 单向链表 """ class Node...self.value = value # 下一个节点 self.next = next class LinkedList(object): """ 链表...self.root) self.root = newNode @property def length(self): """ 获取链表长度...value = linkedlist.getValue(i) print(i, '处的值为: ', value) # ------测试查找某值的索引------- linkedlist.prepend

1.4K7 0

Python实现单向链表

关于链表的介绍，请参考：链表介绍本篇文章使用 Python 来实现一个单向链表。一、定义一个创建节点的类链表是由一个个的节点组成的，在创建链表之前，要先创建节点，然后把节点“串”到链表上。...实现 show() 方法时，为了更形象地展示链表中每个节点的关系，我在相邻两个节点之间使用右箭头连接(空链表无效果)。...同时，上面实现了获取单向链表长度的方法 length()，返回链表当前的节点个数。...index(value)：返回一个数据在链表中的第几个节点，与判断是否存在的实现方式一样，这里返回的是数据处于第几个节点中，如果链表中没有这个数据，则返回-1。...实现的单向链表及单向链表的一些简单操作方法。

9852 0

Python 实现双向链表

usr/bin/env python #-*- coding:utf-8 -*- """ @author:yzk13 @time: 2018/04/18 双向链表 https://blog.csdn.net...self.value = value self.next = None class DoublyLinkedList(object): """ 双向链表类...""" def __init__(self): """ 初始化链表 """ head = Node(None)...self.tail self.tail.pre = self.head @property def length(self): """ 获取链表长度...l.clear() l.print() # 测试长度 print('链表长度为: ', l.length)

1.2K6 0

Python实现双向链表

关于链表的介绍，请参考：链表介绍本篇文章使用 Python 来实现双向链表。一、定义一个创建节点的类链表是由一个一个的节点组成的，在创建链表之前，要先创建节点，然后把节点“串”到链表上。...实现 show() 方法时，为了更形象地展示链表中每个节点的关系，我在相邻两个节点之间使用左箭头加右箭头连接(空链表无效果)。...同时，上面实现了获取双向链表长度的方法 length()，返回链表当前的节点个数。...index(value)：返回一个数据在链表中的第几个节点，与判断是否存在的实现方式一样，这里返回的是数据处于第几个节点中，如果链表中不存在这个数据，则返回-1。...实现的双向链表及双向链表的一些简单操作方法。

5493 0

用python实现单链表的基础操作

1 问题用python实现单链表的基础操作：插入，删除，遍历，判空，清空链表，求长度，获取元素，判断元素是否存在。...2 方法解决问题的步骤采用如下方式：使用函数和类的方法来实现单链表的基本操作插入操作时使用头插法删除操作时，删除头节点一行代码即可，其他位置的需要判断+遍历通过实验、实践等证明提出的方法是有效的..._head is None def length(self): """求链表的长度""" p = self....(9) linklist.remove(5) linklist.travel() linklist.clear() linklist.travel() 3 结语针对用python...实现单链表的基础操作，通过python运行实验，证明该方法是有效的，这种设置方法代码较多，因此未来还需继续改善这种方法以适应更多场景。

1571 0

Python 算法基础篇：链表和双向链表的实现与应用

Python 算法基础篇：链表和双向链表的实现与应用引言链表和双向链表是常用的线性数据结构，它们在算法和程序设计中有着广泛的应用。...本篇博客将重点介绍链表和双向链表的原理、实现以及它们在不同场景下的应用。我们将使用 Python 来演示链表和双向链表的实现，并通过实例展示每一行代码的运行过程。 ❤️ ❤️ ❤️ 1....单向链表的实现与应用 2.1 单向链表的实现下面是单向链表的 Python 实现： class ListNode: def __init__(self, val=0, next=None):...双向链表的实现与应用 3.1 双向链表的实现下面是双向链表的 Python 实现： class DoubleListNode: def __init__(self, val=0, prev=None...我们通过使用 Python 来演示链表和双向链表的实现，并通过实例展示它们在不同场景下的应用。

6582 0

有序链表的实现

有序链表的实现链表的定义依赖于以下结构体： struct Node { struct Node* next; int value; }; 链表依赖一个一个的节点连接而成，由每一个节点中的指向结构体类型的指针指向下一个节点...现在给出n个数字，将它们按照从小到大的顺序依次插入链表中，所需相应函数的声明如下: void insert(struct Node** head, int num); void print_linklist...(struct Node* head); void delete_linklist(struct Node* head); 实现： #include #include struct Node {

3122 0

栈的实现(链表)

本章通过链表实现栈这一数据结构链表链表之前也写了很多文章介绍了，这里基本信息略过，感兴趣的可以去之前的文章了解一下，我这里就假设你们已经对链表和栈很熟悉了。...push在数组中只有一种情况，因为数组是连续的内存空间1，而链表则是根据不同地址的节点链接在一起的，所以这时候我们就要考虑两种情况了。...头部插入或者是尾部插入，尾部插入需要遍历链表所以他的复杂度是O(n)，如果是从头部插入的话复杂度假设O(1)，所以我们选择从头部插入。链表的插入我们已经很清楚了，这里就直接看代码如何实现栈。

1111 0

python实现双向循环链表

www.cnblogs.com/symkmk123/p/9693872.html#4080149 # -*- coding:utf-8 -*- # __author__ :kusy # __content__:双向循环链表实现...self.nHead.next = self.nHead # 表头的前驱后继都是自己 self.node = self.nHead # 节点数目...def size(self): return self.nCount # 判断链表是否为空 def is_empty(self): return self.nCount...print(i, ':', dlt.get(i)) print('size:', dlt.nCount) 执行结果如下 C:\Users\suneee\AppData\Local\Programs\Python...\Python36\python.exe E:/wangjz/PyWorkSpace/LearnPython/PY0929/double_linktable.py -------------------

6763 0

链表的插入实现

，将链表中最后一个节点与新开辟的节点相连接 currentNode->next = node; //将记录当前位置的指针指向新的节点 currentNode = currentNode->next...,int oldVal,int newVal) { //第一种插入实现 if (headNode == NULL) { return; } //遍历链表查看链表中是否存储有oldval，有就将...：\n"); for_each_linkList(headNode); return 0; } 正常找到oldVal插入的情况：可以成功实现 ?...，将链表中最后一个节点与新开辟的节点相连接 currentNode->next = node; //将记录当前位置的指针指向新的节点 currentNode = currentNode->next...,int oldVal,int newVal) { //第一种插入实现 if (headNode == NULL) { return; } //遍历链表查看链表中是否存储有oldval，有就将

4331 0

点击加载更多

扫码

添加站长进交流群

领取专属 10元无门槛券

手把手带您无忧上云

扫码加入开发者社群

相关资讯

热门标签

活动推荐

运营活动

活动名称

广告关闭