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

如果我传递的是slow.next而不是mid,为什么合并排序不起作用?

如果传递的是slow.next而不是mid,合并排序可能不起作用的原因是因为在合并排序算法中,我们需要将链表分成两部分,分别进行排序,然后再将两个有序的链表合并成一个有序的链表。

在传递slow.next而不是mid的情况下,我们实际上将链表分成了两个不均匀的部分。slow.next相当于将链表从中间位置断开,将后半部分作为一个新的链表。而mid则是链表的中间节点,将链表分成了两个长度相等的部分。

由于合并排序算法是基于递归的,当我们传递slow.next时,递归的终止条件可能会发生变化。在正常情况下,当链表只有一个节点或者为空时,递归终止。但是如果我们传递slow.next,那么当链表只有一个节点时,递归并不会终止,而是继续进行下去,导致排序结果不正确。

因此,为了保证合并排序的正确性,我们应该传递mid而不是slow.next作为参数进行递归。这样可以确保链表被正确地分成两个相等长度的部分,并最终得到正确的排序结果。

关于链表的合并排序算法,可以参考腾讯云的相关产品:腾讯云云原生数据库 TDSQL-C,它是一种高性能、高可用、弹性伸缩的云原生数据库产品,适用于各种在线业务场景。产品介绍链接地址:https://cloud.tencent.com/product/tdsqlc

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

相关·内容

双指针+归并排序!图解排序链表!

找到中间节点后,切断 分别再用归并排序,排左右子链表 合并子链表 使用归并排序算法,如何找到中间节点? 我们可以使用双指针法,即一个快指针,一个慢指针。 快指针每次走两步,而慢指针一次只走一步。...如图: 因此代码可以这么写: //slow节点的next指针,指向mid ListNode mid = slow.next; slow.next = null; 分别再用归并排序,排左右子链表 假设我们本来的排序方法是...//排序左右子链表 ListNode leftList = sortList(head); ListNode rightList = sortList(mid); 合并子链表 我们要合并两个都有序的子链表...图解合并过程 我还是画个示意图吧,这样好理解一点。...next指针,指向mid ListNode mid = slow.next; //切断链表 slow.next = null;

38220

面试官系列 - LeetCode链表知识点&题型总结

而不能知道简单的 API。 接着,掌握了这些基本的数据结构之后,一些基本的算法你也要掌握以下,比如快速排序,归并排序,对排序,二分查找。这些基本的一定要掌握,面试当中经常也会问到。...在本题中,设置快指针走两步,慢指针一次走一步,如果快指针走到了尽头,则说明链表无环,如果快指针和慢指针相遇就说明链表有环。为什么呢?...思考:快排和归并排序的时间复杂度都是O(nlogn),实践证明快排的速度比归并排序的速度更快,对于数组排序成立,为什么在链表中归并排序更快呢?...一是,可以很快地进行元素的读取(相对于链表,数组的元素是顺序摆放的,而链表的元素是随机摆放的),数组的partion这步就比链表的partion这步快。...二是,归并排序在merge阶段需要辅助数组,需要申请O(N)的空间,申请空间也是需要时间的。而快排不需要额外申请空间。如果待排序的元素存储在链表中,快排的优点就变成了缺点。

68810
  • 力扣148——排序链表

    ,对于时间复杂度和空间复杂度有要求,针对O(n log n),让我想到了归并排序和快速排序,接下来我们各自来看看。...归并排序,说白了,就是先分解到最小单元,然后逐个进行合并并排序,这样在合并的时候,其实两个链表本身就是有序的,那么当有一个全部取完后,另一个可以直接拼接在最后面。...归并排序——优化 针对上面的代码,在分隔的时候,设置fast = head.next.next,这是因为我们设置的递归终止条件是针对null或者单个节点的。...我猜测是测试数据离散程度更高,这样归并排序的话,并没有充分利用其特性: 当两个链表合并时,如果一个链表已经全部结束,另一个链表剩余的部分可以直接拼接。...总结 以上就是这道题目我的解答过程了,不知道大家是否理解了。针对它的时间复杂度要求,利用归并排序或者快速排序解决。 有兴趣的话可以访问我的博客或者关注我的公众号,说不定会有意外的惊喜。

    34610

    双指针技巧直接秒杀五道算法题

    其实,鼎鼎有名的「滑动窗口算法」就是一种双指针技巧,我们之前的爆文 我写了套框架,把滑动窗口算法变成了默写题 就有这么一段: 我把双指针技巧再分为两类,一类是「快慢指针」,一类是「左右指针」。...说句题外话,之前还有读者争论为什么是环长度整数倍,我举个简单的例子你就明白了,我们想一想极端情况,假设环长度就是 1,如下图: 那么fast肯定早早就进环里转圈圈了,而且肯定会转好多圈,这不就是环长度的整数倍嘛...slow; } 当链表的长度是奇数时,slow恰巧停在中点位置;如果长度是偶数,slow最终的位置是中间偏右: 寻找链表中点的一个重要作用是对链表进行归并排序。...回想数组的归并排序:求中点索引递归地把数组二分,最后合并两个有序数组。对于链表,合并两个有序链表是很简单的,难点就在于二分。 但是现在你学会了找到链表的中点,就能实现链表的二分了。...不过这类算法是有框架模板的,而且前文 我写了首诗,把滑动窗口算法变成了默写题 就讲解了「滑动窗口」算法模板,帮大家秒杀几道子串匹配的问题,如果没有看过,建议去看看。 三连走起~

    30710

    LeetCode链表知识点&题型总结

    前言 刚开始准备刷算法题目的时候,感觉真的是好难,十道题目有九道是不会的。心中曾一万只草泥马跑过,自己怎么这么辣鸡。 慢慢得,我发现算法也是一个可以通过练习慢慢成长的。...在本题中,设置快指针走两步,慢指针一次走一步,如果快指针走到了尽头,则说明链表无环,如果快指针和慢指针相遇就说明链表有环。为什么呢?...思考:快排和归并排序的时间复杂度都是O(nlogn),实践证明快排的速度比归并排序的速度更快,对于数组排序成立,为什么在链表中归并排序更快呢?...一是,可以很快地进行元素的读取(相对于链表,数组的元素是顺序摆放的,而链表的元素是随机摆放的),数组的partion这步就比链表的partion这步快。...二是,归并排序在merge阶段需要辅助数组,需要申请O(N)的空间,申请空间也是需要时间的。而快排不需要额外申请空间。如果待排序的元素存储在链表中,快排的优点就变成了缺点。

    1.6K10

    每日三题-环形链表I、环形链表II、排序链表

    ‍个人主页: 才疏学浅的木子 ‍♂️ 本人也在学习阶段如若发现问题,请告知非常感谢 ‍♂️ 本文来自专栏: 算法 算法类型:Hot100题 每日三题 环形链表I 环形链表II 排序链表...如果相遇那个方法是第一种的话,即quick = head.next 那么quick需要在相遇之后再向移动一个位置,推到如上 public class Solution { public ListNode...; } } 排序链表 解法一 使用优先队列 先循环一遍把当前节点放进去,再重构有序链表 class Solution { public ListNode sortList(ListNode...mid = slow.next; slow.next = null; // 将一个链表断开为两个链表 ListNode left = sortList(head);...ListNode right = sortList(mid); // 相当于两个有序链表的合并 ListNode res = new ListNode();

    17920

    前端算法系统练习: 链表篇完结

    但是现在如果面对的是一个复杂的工程问题,需要你来开发一个辅助业务的脚手架工具,改造框架源码来提高项目的扩展性,或者面对严重的性能问题能马上分析出原因,然后给出解决的思路并在不同因素中平衡,这些都不是一个业余的玩家能够在短时间内胜任的...k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原有顺序。...,返回合并后的排序链表。...在这里需要提醒大家的是,在自下而上的实现方式中,我为每一个链表绑定了一个虚拟头指针(dummyHead),为什么这么做?...这是为了方便链表的合并,比如 l1 和 l2 合并之后,合并后链表的头指针就直接是 l1 的 dummyHead.next 值,等于说两个链表都合并到了 l1 当中,方便了后续的合并操作。

    35510

    排序链表 算法解析

    大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。...这道题要求时间复杂度更低的排序算法,要求达到O(n log n)的时间复杂度。 可以实现O(n log n)的时间复杂度的排序算法有归并排序、堆排序和快速排序,其中最适合链表的排序算法是归并排序。...首先来了解一下什么是归并排序,归并排序是自顶向下直接合并的方式进行排序,具体过程如下: 1、找到链表中点,以中点为界,将链表拆成两个子链表。 2、对两个子链表分别排序。...3、将两个排序后子链表合并,得到完成链表。 因为上述的过程是通过递归实现的,所以时间复杂度为O(n log n),空间复杂度为O(log n)。...空间复杂度:O(log n) 其中n是链表的长度,空间复杂度主要取决于递归调用的栈空间。 三、总结 通过递归实现链表的归并排序,主要分成两步。 第一步是分割成两个子链表。

    23910

    链表总计

    K个排序链表 直接对K个排序链表进行两两合并,调用两两合并的方法 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode...(归并排序) 使用迭代归并排序进行链表排序 public ListNode sortList(ListNode head){ // 如果头为空,或者只有一个节点,直接返回...// 这里slow 和 fast 并驾齐驱出发,那么slow所到达的点是下一半的起点,否则fast快slow一步slow到达是上一半终点 ##### 这里注意一点需要判断 链表的个数是不是奇数个主要采用判断...fast是不是为null,在一同出发的时候,如果fast 为 null 说明为偶数,fast不为null,说明链表个数为奇数个。...l2 : l2.next, head); int temp = l1.val + l2.val + node.val / 10;//计算当前节点的值,node.val是上一个节点的值,如果

    47510

    每日一题《剑指offer》链表篇之合并k个已排序的链表

    数据范围 数据范围:节点总数 0≤n≤5000,每个节点的val满足 ∣val∣<=1000 要求:时间复杂度O(nlogn) 举例 解题思路 方法一:归并排序 如果是两个有序链表合并,我们可能会利用归并排序合并阶段的思想...既然都是归并排序的思想了,那我们可不可以直接归并的分治来做,而不是顺序遍历合并链表呢?答案是可以的! 归并排序是什么?简单来说就是将一个数组每次划分成等长的两部分,对两部分进行排序即是子问题。...方法二:优先队列 如果非要按照归并排序的合并思路,双指针不够用,我们可以直接准备kkk个指针,每次比较得出kkk个数字中的最小值。...容器中的元素是有序的,如果是小顶堆,顶部元素就是最小的,每次可以直接取出最小的元素。...如果是普通线形链表末尾一定有NULL,那我们可以根据链表中是否有NULL判断是不是有环。 但是,环形链表遍历过程中会不断循环,线形链表遍历到NULL结束了,但是环形链表何时能结束呢?

    22810

    七十一、去重交换排序链表、 求链表的中间结点

    「@Author:Runsen」 ❝编程的本质来源于算法,而算法的本质来源于数学,编程只不过将数学题进行代码化。...如果它是重复的,我们更改当前结点的 next 指针,以便它跳过下一个结点并直接指向下一个结点之后的结点。...归并排序分为两步, 1.找到待排序链表的中间节点(使用快慢指针法,leetcode 876题) 2.合并两个有序链表(leetcode 21题),因此本题相当于结合这两步来实现链表排序。...首先,遍历整个链表,确定链表中元素个数,同时也可以确定链表的中间位置;然后从中间位置切断链表(mid->key=NULL);然后递归地给两个链表进行排序;最后,合并两个有序链表,形成一个完整的有序链表。...整个算法的时间复杂度为O(n long),空间复杂度为O(1)。 「人生最重要的不是所站的位置,而是内心所朝的方向。

    44730

    排序链表

    题目源:https://leetcode-cn.com/problems/sort-list ---- 给你链表的头结点 head ,请将其按 升序 排列并返回 排序后的链表 。...5 <= Node.val <= 10^5 思路: 题目问题是排序单链表,单链表的性质是从前往后查找元素 解题思路1 :链表问题简单的做法是使用辅助空间list来解决,但是会消耗空间 # Definition...,merge sort,然后递归 即 首先将链表从中间断开,两边分别排序后,再进行链表合并; 排序可以用两种方式:递归方式与非递归方式 递归方式: # Definition for singly-linked...fast = fast.next.next mid = slow.next slow.next = None # 截断 #...,不用递归 h = head length = 0 # 长度用来结束迭代,当需要处理的长度大于length时候,结束排序 intv = 1 # 此时的元素个数

    28730

    Leetcode No.148 排序链表(归并)

    题目的进阶问题要求达到 O(nlogn) 的时间复杂度和 O(1)的空间复杂度,时间复杂度是O(nlogn) 的排序算法包括归并排序、堆排序和快速排序(快速排序的最差时间复杂度是 O(n^2),其中最适合链表的排序算法是归并排序...归并排序基于分治算法。最容易想到的实现方式是自顶向下的递归实现,考虑到递归调用的栈空间,自顶向下归并排序的空间复杂度是 O(logn)。...如果要达到 O(1) 的空间复杂度,则需要使用自底向上的实现方式。 方法一:自顶向下归并排序 对链表自顶向下归并排序的过程如下。 找到链表的中点,以中点为分界,将链表拆分成两个子链表。...将两个排序后的子链表合并,得到完整的排序后的链表。可以使用「21. 合并两个有序链表」的做法,将两个有序的子链表进行合并。 上述过程可以通过递归实现。...如果每个长度为subLength 的子链表已经有序,合并两个长度为 subLength 的有序子链表,得到长度为 subLength×2 的子链表,一定也是有序的。

    25010

    LeetCode109:有序列表转二叉搜索树

    题目描述 给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。 本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。...题目中描述了,所谓的二叉搜索树是一种对所有结点左右子树深度都不超过1,且左子树值都不超过根结点的值,右子树的值都不小于根结点的值。 第二、明确题目中给出的单链表是升序。...因为是单链表结构,并不是数组结构,所以查找中间结点需要进行遍历查找才行。那么我们是不是可以将单链表结构的数据转换成数组结构呢?这样岂不是查找起来比较容易吗?...,由于是已经排序好的单链表,首先获取全部的排序元素值,然后根据取中间元素构建根节点,依次进行递归迭代左右结点即可 def helper(vals): if vals...既然是中间结点,那么就是整个单链表的中间元素,我们如果知道整个链表长度,然后再遍历一次链表取中间长度的岂不是就可以了吗?但是这样势必会花费更多的时间,从而导致效率低下。

    91430

    数组双指针直接秒杀七道题目

    所谓左右指针,就是两个指针相向而行或者相背而行;而所谓快慢指针,就是两个指针同向而行,一快一慢。...比如说看下力扣第 26 题「删除有序数组中的重复项」,让你在有序数组去重: 函数签名如下: int removeDuplicates(int[] nums); 简单解释一下什么是原地修改: 如果不是原地修改的话...由于数组已经排序,所以重复的元素一定连在一起,找出它们并不难。但如果毎找到一个重复元素就立即原地删除它,由于数组中删除元素涉及数据搬移,整个时间复杂度是会达到O(N^2)。...GIF 图: 再简单扩展一下,看看力扣第 83 题「删除排序链表中的重复元素」,如果给你一个有序的单链表,如何去重呢?...如果回文串的长度为奇数,则它有一个中心字符;如果回文串的长度为偶数,则可以认为它有两个中心字符。

    52610

    面试必备:高频算法题汇总「图文解析 + 教学视频 + 范例代码」必问之 链表 + 栈 + 队列 部分!

    = null){ fast = fast.next.next; slow = slow.next; } return slow; } ---- 合并两个已排序链表...归并排序 归并排序的也是基于分治的思想,但是与快排不同的是归并是先划分,然后从底层开始向上合并。...归并排序的主要思想是将两个已经排好序的分段合并成一个有序的分段。除了找到中间节点的操作必须遍历链表外,其它操作与数组的归并排序基本相同。...如果栈顶的元素是一个 相同类型的 左括号,那么我们将它从栈中弹出并继续处理。否则,这意味着表达式无效。 如果到最后我们剩下的栈中仍然有元素,那么这意味着表达式无效。...Android 属性动画框架 ObjectAnimator、ValueAnimator ,这一篇就够了 看完这篇再不会 View 的动画框架,我跪搓衣板 请点赞!因为你的鼓励是我写作的最大动力!

    25520

    归并排序的迭代(非递归)实现

    对整个数组进行一次小长度的Merge算法后,可以构成一个长度翻倍的Merge算法的条件而进行Merge算法,最终对整个数组实现排序。 归并排序的流程图 下面是归并排序的流程图。 ?...//因归并排序的第一步是划分,步长一步步翻倍 //因待排序的数组的长度可能是奇数,而步长总是2的整数倍,故将step的上限定为数组长度的一半并向上取整,即c.length/2 + 1 while(step...(一)step的界限控制 step是用来控制分割的关键参数,因原数组的长度可能为奇数,而step总是2的整数次幂,所以若不进行区别控制,将会导致最后结果为一个可以分割成两个已排序的子数组的新数组,而没有进行最后的一步归并排序...若不向上取整,则3/2 = 1,只排序1次,所以结果必然是错误的。 2、原数组:5 2 4 6,数组长度为4,是偶数,且4/2+1 = 3,而step为2的整数次幂,所以排序次数为2次。...为什么这里是step/2?

    1.5K30
    领券