双指针+归并排序!图解排序链表!
前言
大家好,我是捡田螺的小男孩,今天我们来看一道很经典的leetcode真题:排序链表
公众号:捡田螺的小男孩
题目
给你链表的头结点head
,请将其按 升序 排列并返回 排序后的链表 。要求时间复杂度是O(n log n)
实例1:
输入:head = [4,2,1,3] 输出:[1,2,3,4]复制代码
实例2:
输入:head = [-1,5,3,4,0] 输出:[-1,0,3,4,5]复制代码
分析
排序算法选定
时间复杂度要求是O(n log n)
,我们很容易想到快速排序,以及归并排序。
我们先来回顾下快速排序
,它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
也就是说,快速排序需要找到基准值,一部分数据比这个基准值小,一部分数据比这个基准值大。因为这个是个链表,发现即使找完基准值,也不好操作。因此,可以考虑使用归并排序算法。
归并排序算法核心步骤
归并排序核心步骤如下:
把长度为n的要排序的序列,分成两个长度为n/2的子序列;
对这两个子序列,分别采用归并排序;
将两个排序好的子序列,合并成一个最终有序的排序序列。
对于链表来说,不同于一般的数据序列,它找到中间节点之后,需要切断一下。因此用归并排序算法,去排链表的操作大概是这样:
遍历链表,找到中间节点。
找到中间节点后,切断
分别再用归并排序,排左右子链表
合并子链表
使用归并排序算法,如何找到中间节点?
我们可以使用双指针法,即一个快指针,一个慢指针。
快指针每次走两步,而慢指针一次只走一步。当快指针走到链表末节点的时候,慢指针是不是走到中间节点啦。
因此,找到链表中间节点的代码,我们可以这么写:
ListNode slow = head; ListNode fast = head; while(fast.next!=null && fast.next.next !=null){ fast = fast.next.next; slow = slow.next; }复制代码
找到中间节点后,切断
找到中间节点后,如何切断呢?
我们可以把slow
节点的next
指针,赋给新的变量mid
,然后再slow
的next
指针指向空,就可以切断啦。如图:
因此代码可以这么写:
//slow节点的next指针,指向mid ListNode mid = slow.next; slow.next = null;复制代码
分别再用归并排序,排左右子链表
假设我们本来的排序方法是sortList
,那我们找到head和mid子链表后,那需要用同样方法区排序这两个子链表嘛。
//排序左右子链表 ListNode leftList = sortList(head); ListNode rightList = sortList(mid);复制代码
合并子链表
我们要合并两个都有序的子链表,把它变成一个新的有序的链表,其实可以借助一个中间链表,然后分别遍历左、右子链表,比较两个链表当前节点的值,哪个小的话,把它写到中间链表,并且值小的节点所在的链表,继续遍历下一个节点。
图解合并过程
我还是画个示意图吧,这样好理解一点。
假设要排序的左、右链表,以及中间链表如下:
首先取左链表的值1,与右链表的值3比较,因为1<3
,所以把值为1
的节点放到中间链表,并且左链表移动一个节点,中间链表也右移一个节点,如图:
接着呢,取左链表的值5,与右链表的值3比较,因为5>3
,所以把值为3
的节点放到中间链表,并且右链表移动一个节点,中间链表也移动一个节点,如图:
接下来呢,取左链表的值5,与右链表的值4比较,因为5>4
,所以把值为4
的节点放到中间链表,并且右链表移动一个节点,中间链表也移动一个节点,如图:
紧接者,取左链表的值5,与右链表的值6比较,因为5<6
,所以把值为5
的节点放到中间链表,并且左链表移动一个节点,中间链表也移动一个节点,如图:
最后,因为左链表已经遍历完啦,右链表还没有,因此把右链表放到中间链表即可(官方点来说,就是中间链表的next指针指向右链表),如图:
这时候,链表已经合并完啦,但是还不是我们想要的,因为多了个初始节点0
,并且指针指向了5
。怎么办呢?我们要的是1-> 3-> 4 ->5 ->6
。
我们可以初始化的时候,把链表head
赋给一个temp
嘛,然后让temp
去移动,最后返回head的next
就可以啦,如图:
合并代码实现
我们根据图解的过程,来实现下代码吧,如下:
public ListNode merge(ListNode left, ListNode right) { //初始化head链表,合并用 ListNode head = new ListNode(0); //把head 赋给中间变量temp ListNode temp = head; while (left != null && right != null) { //比较左、右子链表,当前指针指向节点的值大小 if (left.val <= right.val) { //temp 指向值小的节点(左链表的值小) temp.next = left; //左链表右移一个节点 left = left.next; } else { //temp 指向值小的节点(右链表的值小) temp.next = right; //右链表右移一个节点 right = right.next; } //中间链表指针跟着往下移动一个节点 temp = temp.next; } //退出循环后,表示左子链表和右子链表至少一个遍历完了 //如果左子链表不为空,那把temp的next指针指向它 if (left != null) { temp.next = left; //如果右子链表不为空,那把temp的next指针指向它 } else if (right != null) { temp.next = right; } //最后返回head的next指针,就是合并后的链表啦 return head.next; }复制代码
如果代码还有不理解的地方,可以回头再看看图解过程哈。
完整代码实现
通过遍历链表找到中间节点、中间节点切断链表、分别用归并排序排左右子链表、合并子链表,我们可以整合一下,得出完整代码,如下:
class Solution { public ListNode sortList(ListNode head) { //如果链表为空,或者只有一个节点,直接返回即可,不用排序 if (head == null || head.next == null) return head; //快慢指针移动,以寻找到中间节点 ListNode slow = head; ListNode fast = head; while(fast.next!=null && fast.next.next !=null){ fast = fast.next.next; slow = slow.next; } //找到中间节点,slow节点的next指针,指向mid ListNode mid = slow.next; //切断链表 slow.next = null; //排序左子链表 ListNode left = sortList(head); //排序左子链表 ListNode right = sortList(mid); //合并链表 return merge(left,right); } public ListNode merge(ListNode left, ListNode right) { ListNode head = new ListNode(0); ListNode temp = head; while (left != null && right != null) { if (left.val <= right.val) { temp.next = left; left = left.next; } else { temp.next = right; right = right.next; } temp = temp.next; } if (left != null) { temp.next = left; } else if (right != null) { temp.next = right; } return head.next; } }复制代码
去leetcode提交一下,找找成就感,通过啦,哈哈。
作者:捡田螺的小男孩
链接:https://juejin.cn/post/7031336438222290951