Sort List
sort a linked list in O(n log n) time using constant space complexity.
排序,时间复杂度为n(logn),
我们知道堆排序,归并排序即使在最坏的情况下时间复杂度为n(logn)。
这里使用链表的归并排序实现。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode sortList(ListNode head) { if(head==null) return null; if(head.next==null) return head; ListNode p = head; ListNode q = head; while(q.next!=null&&q.next.next!=null) { p=p.next; q=q.next.next; } q=p.next; p.next=null; p=head; p=sortList(p); q=sortList(q); return merge(p,q); } public ListNode merge(ListNode p,ListNode q) { ListNode r = new ListNode(0); ListNode res = r; while(p!=null||q!=null) { int a,b; if(p==null) a = Integer.MAX_VALUE; else a=p.val; if(q==null) b = Integer.MAX_VALUE; else b=q.val; if(a<=b) { r.next=p; p=p.next; } if(a>b) { r.next=q; q=q.next; } r=r.next; } return res.next; } }
再来熟悉下排序的时间复杂度:
相关推荐
python python_leetcode题解之147_Insertion_Sort_List
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
例如,在解决搜索和排序问题时,Python内置的`list`数据结构和相关的操作函数如`sort()`、`append()`等,能快速实现各种功能。 接着,我们来看数据结构。在LeetCode中,常见的数据结构包括数组、链表、栈、队列、树...
Sort Colors LeetCode 125 Valid Palindrome LeetCode 167 Two Sum II - Input array is sorted LeetCode 344 Reverse String LeetCode 345 Reverse Vowels of a String 2 字符串 编号 题目 LeetCode 3 Longest ...
- **Sort List**:对链表进行排序。 - **Rotate List**:将链表顺时针旋转指定次数。 - **Reorder List**:按照特定规则重新排列链表。 - **Partition List**:将链表按值分割成两个部分。 - **Add Two Numbers...
**1.12 Insertion Sort List (147)** - **问题描述**:对链表进行插入排序。 - **解题思路**: - 创建一个虚拟头节点,用于记录排序后的链表起始位置。 - 依次将原链表中的节点插入到已排序部分的适当位置。 **...
Python的内置数据结构如list、dict、set、tuple等都能在这些题目中大显身手。理解它们的特性和操作方法是解决问题的关键。 2. **递归与回溯**:在算法中,递归和回溯经常用于解决复杂的问题,例如搜索、图遍历或...
如数组(array)、链表(linked list)、字符串(string)、哈希表(hashtable)、栈(stack)、队列(queue)、二叉树(binary tree)、图(graph)、动态规划(DP)、数学问题(Math)、双指针技巧(Two Pointers...
2. **C++标准库**:C++标准库提供了大量预先定义的函数和数据结构,如容器(vector、list、set、map)、迭代器、算法(排序、查找)等。在解题过程中,这些工具被广泛用于优化算法和提高代码效率。 3. **数据结构**...
- **STL库**:利用标准模板库(STL)中的容器(如vector、list、set)、算法(如sort、find)和迭代器来简化代码。 - **模板和泛型编程**:当需要编写可重用的代码时,可以使用模板来实现泛型功能。 - **面向对象...
list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡[LeetCode 3. Longest Substring Without Repeating Characters], N/A 2017.06.15 打卡[LeetCode 407. Trapping Rain Water II], BFS/...
STL(标准模板库)提供了丰富的数据结构和算法,如 vector、list、map、set、sort 等,极大地简化了编程工作;同时,C++ 的内存管理更加灵活,允许程序员直接操作指针,这对于理解和优化算法性能非常有帮助。 "cpp-...
- Sort Colors: 给定一个包含红色、白色和蓝色,一共n个元素的数组,原地对它们进行排序,使得相同颜色的元素相邻,并按照红色、白色、蓝色顺序排列。 - Combinations: 从n个不同元素中取出k个元素的组合。 - ...
- **链表(Linked List)**: 由一系列节点组成的集合,每个节点包含数据部分和指向下一个节点的指针。 - **二叉树(Binary Tree)**: 一种树形数据结构,每个节点最多有两个子节点,通常用于实现快速查找和排序操作。 - ...
5. **STL库**:标准模板库(STL)提供了大量现成的数据结构和算法,如容器(vector、list、set等)、算法(sort、find等)和迭代器,熟练运用STL可以简化代码并提高代码质量。 6. **异常处理**:在编写C++代码时,...
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 387_字符串中的第一个唯一字符 链表操作 2 ...删除链表的倒数第N个节点 ...sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
最大公共字符串leetcode leetcode 数组 链表 二叉树 位操作 判断字符串的顺序排列 给定一个字符串数组,将字谜组合在一起。 例如,给定:["eat", "tea", "tan", "ate", "nat", "bat"], public class Solution { ...
- **排序**:快速排序、归并排序、堆排序等都是LeetCode中常遇到的排序算法,C++的`std::sort`函数能处理大部分排序需求。 - **搜索**:线性搜索、二分搜索、深度优先搜索(DFS)和广度优先搜索(BFS)是常用的...
7. **Sort List**:对链表进行排序。可以先将链表转换为数组,然后使用快速排序或归并排序,最后将排序后的数组转换回链表。 8. **Search in Rotated Sorted Array**:在旋转有序数组中查找目标值。理解旋转数组的...