前言:
此时姐妹们对“链表快速排序时间复杂度”都比较珍视,兄弟们都需要了解一些“链表快速排序时间复杂度”的相关知识。那么小编同时在网络上网罗了一些关于“链表快速排序时间复杂度””的相关资讯,希望兄弟们能喜欢,看官们一起来学习一下吧!原题
在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
示例 1:
输入: 4->2->1->3输出: 1->2->3->4
示例 2:
输入: -1->5->3->4->0输出: -1->0->3->4->5
原题url:
解决
题目很明确,排序,对于时间复杂度和空间复杂度有要求,针对O(n log n),让我想到了归并排序和快速排序,接下来我们各自来看看。
对了,这里先统一放一下节点类,单向链表中的节点,存储当前节点的值和后一个节点的引用。
Definition for singly-linked list.public class ListNode { int val; ListNode next; ListNode(int x) { val = x; }}
归并排序
归并排序,说白了,就是先分解到最小单元,然后逐个进行合并并排序,这样在合并的时候,其实两个链表本身就是有序的,那么当有一个全部取完后,另一个可以直接拼接在最后面。
让我们看一下代码:
public class Solution { public ListNode sortList(ListNode head) { // 归并排序 if (head == null || head.next == null) { return head; } // 先分隔,利用快慢指针分隔。 // 快指针先走,因为只有当空节点或1个节点才是终止条件,2个节点的时候,如果不让快指针先走,而是也指向head,那么2个节点永远不会被分隔,会陷入死循环 ListNode fast = head.next.next; ListNode slow = head; while (true) { if (fast == null || fast.next == null) { break; } fast = fast.next.next; slow = slow.next; } // 后半部分的开头 ListNode second = slow.next; second = sortList(second); // 前半部分的开头 slow.next = null; ListNode first = head; first = sortList(first); // 合并 ListNode result = new ListNode(0); head = result; while (first != null && second != null) { if (first.val < second.val) { result.next = first; first = first.next; } else { result.next = second; second = second.next; } result = result.next; } if (first != null) { result.next = first; } else { result.next = second; } return head.next; }}
提交OK,执行用时:5 ms,内存消耗:39.6 MB,执行用时只战胜了59.07%的 java 提交记录,应该还有优化的空间。
归并排序——优化
针对上面的代码,在分隔的时候,设置fast = head.next.next,这是因为我们设置的递归终止条件是针对null或者单个节点的。其实当只剩下两个节点的时候,就可以进行排序了,这样应该可以节省近一半的时间,当然了,从时间复杂度上来说并没有改变。
我们看一下代码:
public class Solution { public ListNode sortList(ListNode head) { // 归并排序 if (head == null || head.next == null) { return head; } // 说明只有两个节点 if (head.next.next == null) { ListNode second = head.next; if (head.val > second.val) { return head; } else { second.next = head; head.next = null; return second; } } // 先分隔,利用快慢指针分隔。 ListNode fast = head; ListNode slow = head; while (true) { if (fast == null || fast.next == null) { break; } fast = fast.next.next; slow = slow.next; } // 后半部分的开头 ListNode second = slow.next; second = sortList(second); // 前半部分的开头 slow.next = null; ListNode first = head; first = sortList(first); // 合并 ListNode result = new ListNode(0); head = result; while (first != null && second != null) { if (first.val < second.val) { result.next = first; first = first.next; } else { result.next = second; second = second.next; } result = result.next; } if (first != null) { result.next = first; } else { result.next = second; } return head.next; }}
执行用时,有的时候是4 ms,有的时候是3 ms,看来归并排序这条路差不多就是这样了。
快速排序
快速排序的思想就是选择一个标准值,将比它大的和比它的小的,做交换。针对链表这种结构,就是将比它大的放在一个链表中,比它小的放在一个链表中,和它一样大的,放在另一个链表中。然后针对小的和大的链表,继续排序。最终将三个链表按照小、相等、大进行连接。
接下来让我们看看代码:
class Solution { public ListNode sortList(ListNode head) { // 利用快排 // 单个节点是终止节点 if (head == null || head.next == null) { return head; } // 比标准值小的节点 ListNode lowHead = new ListNode(0); ListNode low = lowHead; // 和标准值一样的节点 ListNode midHead = new ListNode(0); ListNode mid = midHead; // 比标准值大的节点 ListNode highHead = new ListNode(0); ListNode high = highHead; // 标准值 int val = head.val; ListNode node = head; // 遍历 while (node != null) { // 比标准值大的节点 if (node.val > val) { high.next = node; high = high.next; } // 比标准值小的节点 else if (node.val < val) { low.next = node; low = low.next; } // 和标准值一样的节点 else { mid.next = node; mid = mid.next; } node = node.next; } // 终止,避免造成环 low.next = null; high.next = null; lowHead.next = sortList(lowHead.next); highHead.next = sortList(highHead.next); // 找出小节点链表的末尾 low = lowHead; while (low.next != null) { low = low.next; } // 拼接 low.next = midHead.next; mid.next = highHead.next; return lowHead.next; } }
提交OK,执行用时:2 ms,内存消耗:40.01 MB。
和归并排序相比,时间更短,至于原因,我确实是没有想明白,因为都需要比较,然后重新构造新链表。我猜测是测试数据离散程度更高,这样归并排序的话,并没有充分利用其特性:
当两个链表合并时,如果一个链表已经全部结束,另一个链表剩余的部分可以直接拼接。
总结
以上就是这道题目我的解答过程了,不知道大家是否理解了。针对它的时间复杂度要求,利用归并排序或者快速排序解决。
有兴趣的话可以访问我的博客或者关注我的公众号、头条号,说不定会有意外的惊喜。
公众号:健程之道
标签: #链表快速排序时间复杂度 #链表排序最好时间复杂度 #链表排序最快 #链表排序复杂度