原题链接:#148 Sort List
要求:
给一个单向链表排序,要求时间复杂度为O(nlogn)且空间复杂度为O(1)。
单向链表定义如下:
class ListNode{ int val; ListNode next; ListNode(int x){ this.val = x; } }
难度:中等
分析:
若没有时间复杂度及空间复杂度的限制,解法将会很多。譬如先遍历一遍链表,将其所有元素放在一个数组内,以任一种排序算法排序后重新生成单向链表,比如最简单的冒泡。这种思路并非不可取,毕竟出于解决问题的角度它体现了一种转化的思想,把链表操作转化为数组操作并用开发人员自己最熟悉且用起来最舒服的算法排序并能切实解决问题,并不能全盘否定。这种解决方案的时间复杂度为O(n2),空间复杂度为O(n)。
题目加上了时间和空间两方面的限制,就要求我们优化一下算法了。同时,既然参数是链表,要求返回值也是链表,实在没有必要使用其他的数据结构来回转换。既满足时间复杂度要求又不需要O(n)辅助数据结构的,考虑采用归并排序算法。
各种排序算法的时间复杂度和空间复杂度比较:
图片来自:vincent-cws
解决方案:
Java - 384ms
public ListNode sortList(ListNode head) { if(head==null||head.next==null){ return head; } int nodeSum = 0; ListNode tmp = head; while(tmp!=null){ tmp = tmp.next; nodeSum++; } tmp = head; for(int i=1; i<nodeSum/2; i++){ tmp=tmp.next; } ListNode l1 = head; //将原链表分拆为两个子链表,分别排序然后合并 ListNode l2 = tmp.next; tmp.next=null; ListNode result = merge(sortList(l1), sortList(l2)); return result; } public ListNode merge(ListNode l1, ListNode l2){ ListNode head = new ListNode(0); ListNode cursor = head; while(l1!=null&&l2!=null){ if(l1.val<l2.val){ cursor.next=l1; l1 = l1.next; }else{ cursor.next=l2; l2=l2.next; } cursor = cursor.next; } if(l1!=null){ cursor.next = l1; }else { cursor.next = l2; } return head.next; }
相关推荐
1.1常数级链表排序Sort a linked list in O(n log n) time using constant space complexity.
leetcode题库 LeetCode-PHP 坚持每天做算法题 (๑╹ヮ╹๑)ノ Studying makes me happy 文件夹 Array 数组 Backtracking 回溯算法 Binary Search 二分查找 Bit Manipulation 位运算 Breadth First Search 广度优先...
利用java中Array对象的sort方法排序,使得整个数组呈升序状态 - 再利用两段取点相加的sum与target比较 - 若大于target,则后结点前移,sum变小 - 若小于target,则前结点后移,sum变大 逐个试,向中间逼近...
leetcode 答案 leetcode Day 1 两数之和: 1。 考虑两层嵌套循环 2。 用dictionary以及 enumerate 函数 def twoSum1(self, nums: List[int], target: int) -> List[int]: dct ={} for index, number in enumerate...
sort--排序 stackqueue--栈和队列 string--串 tree--树 leetcode_agorithm leetcode算法示例题解 数据机构 线性表 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,...
Collections.sort(List,Comparator) 对列表进行排序 反向链表(给定链表反向部分的长度) ListNode start = pre.next; ListNode then = start.next; //key part of reversing given length linkedlist for(int i =...
insertion-sort-list 树 binary-tree-postorder-traversal 树 binary-tree-preorder-traversal 链表 linked-list-cycle-ii 链表 linked-list-cycle 链表 copy-list-with-random-pointer 复杂度 single-number 动态...
sort--排序 stackqueue--栈和队列 string--串 tree--树 leetcode_agorithm leetcode算法示例题解 数据机构 线性表 线性表是最基本、最简单、也是最常用的一种数据结构。线性表中数据元素之间的关系是一对一的关系,...
leetcode 分类 Leetcode 介绍 leetcode个人题解,根据leetcode给的标签进行分类,按照数据结构对题目进行求解。 软件架构 软件架构说明 ...sort:排序算法 heap: 堆的应用题解 安装教程 clone IDEA JDK 8
leetcode下载 Leetcode 刷题记录 01. Two Sum 暴力破解时间复杂度高,使用hash表降低时间复杂度 02. Add Two Numbers 由于链表是逆置的,所以直接顺序遍历两个链表,按照加法器规则依次相加各节点,并进位 最后一组...
leetcode中国 LeetCode 最近在进行 LeetCode 和力扣中国的每日一题,如果有共同刷题的小伙伴可以点击 一起参与。 我对题目进行了标签分类,你也可以按 进行刷题。 数组 ( Array ) 链表 ( Linked List ) 栈 ( Stack )...
Arrays.sort(Object[])和Collections.sort(List)保证是稳定的。 如果需要部分排序,这对于保留原始排序很有用: 堆 对于Java,数据结构是PriorityQueue; 对于 Python,请参阅 heapq 中的函数 K 最小/最大元素来自:...
leetcode 答案About Me 我叫做林宏霖,绰号是呱呱。 我喜欢打排球,最喜欢的食物是芒果 我有一个很可爱的女友 Week1 中秋节放假 课程、分数说明 Week2 Linked List Linked list(连结串列)是一种常见的资料结构,其...
leetcode 分类 ReadMe 纯粹记录一下自己leetCode做题记录及部分思路笔记,不充当指导性repo 加油!:sunrise_over_mountains: easy mid hard 7 36 4 :memo: sliding window 滑动窗口 two point 双指针 fast&slow ...
leetcode ...7:选择排序selectsort 8:快排—quicksort 9:二叉树实现—BinaryTree 10:字符串实现—Astring 11:简单的向量—vector 12:cup进程调度(优先级,轮转,先来先服务)—cpu-RR leetcode算法
leetcode下载 Algorithm 记录一些很有意思的小代码.包括一些常见的面试题,及一些奇技淫巧. csy.array:数组相关 ...csy.sort:八大经典排序算法 csy.stack:最小栈 csy.string:KMP算法 csy.tree:树相关 csy.ufs:并查集的
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 387_字符串中的第一个唯一字符 链表操作 2 ...删除链表的倒数第N个节点 ...sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
leetcode中国 每周小测 每周题目 week 1 adjust : 将数组中指定索引处的值替换为经函数变换的值 实现版本: ramda版本参考: groupAnagrams : 给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但...
leetcode 答案myDataStructure 本程式库希望收集各种常用的资料结构方便使用, 程式全用c++写成 基础资料结构 收集一般资料结构课程会学到的东西 资料结构/演算法 程式 可参考题目(验证程式正确性) 二分搜索 排序...
LeetCodeLeetCode solutions(Java)树Minimum Depth of Binary Tree栈evaluate-reverse-polish-notation穷举max-points-on-a-line链表sort-list排序insertion-sort-list树binary-tree-postorder-traversal树binary-...