【题目】
Sort a linked list inO(nlogn)
time using constant space complexity.
【分析】
单链表适合用归并排序,双向链表适合用快速排序。本题可以复用Merge Two Sorted Lists方法
【代码】
/*********************************
* 日期:2015-01-12
* 作者:SJF0115
* 题目: 148.Sort List
* 来源:https://oj.leetcode.com/problems/sort-list/
* 结果:AC
* 来源:LeetCode
* 博客:
**********************************/
#include <iostream>
#include <climits>
using namespace std;
struct ListNode{
int val;
ListNode *next;
ListNode(int x):val(x),next(NULL){}
};
class Solution {
public:
ListNode *sortList(ListNode *head) {
// 容错处理
if(head == NULL || head->next == NULL){
return head;
}//if
// 定义两个指针
ListNode *fast = head,*slow = head;
// 慢指针找到中间节点
while(fast->next != NULL && fast->next->next != NULL){
// 快指针一次两步
fast = fast->next->next;
// 慢指针一次一步
slow = slow->next;
}//while
// 从中间节点断开
fast = slow->next;
slow->next = NULL;
// 前段排序
ListNode *left = sortList(head);
// 后段排序
ListNode *right = sortList(fast);
// 前后段合并
return mergeTwoLists(left,right);
}
private:
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode *head = new ListNode(-1);
for(ListNode *p = head;l1 != NULL || l2 != NULL;p = p->next){
int val1 = (l1 == NULL) ? INT_MAX : l1->val;
int val2 = (l2 == NULL) ? INT_MAX : l2->val;
if(val1 <= val2){
p->next = l1;
l1 = l1->next;
}//if
else{
p->next = l2;
l2 = l2->next;
}//else
}//for
return head->next;
}
};
int main(){
Solution solution;
int A[] = {8,3,10,5,11,1,4};
// 链表
ListNode *head = new ListNode(A[0]);
ListNode *p = head;
for(int i = 1;i < 7;i++){
ListNode *node = new ListNode(A[i]);
p->next = node;
p = node;
}//for
head = solution.sortList(head);
// 输出
p = head;
while(p){
cout<<p->val<<" ";
p = p->next;
}//while
cout<<endl;
return 0;
}
分享到:
相关推荐
148. Sort List Leetcode 56. Merge Intervals 进阶题目: Leetcode 179. Largest Number Leetcode 75. Sort Colors Leetcode 215. Kth Largest Element Leetcode 4. Median of Two Sorted Arrays 注意:后两题是与...
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/...
看leetcode吃力资料结构与演算法学习笔记 Week1 中秋节放假 Week2 说明上课方式与计分规则 Week3 完成LeetCode 707. Design Linked List Week4 完成LeetCode 155. Min Stack 完成LeetCode 232. Implement Queue ...
* [Linked List](https://github.com/kamyu104/LeetCode#linked-list) * [Stack](https://github.com/kamyu104/LeetCode#stack) * [Queue](https://github.com/kamyu104/LeetCode#queue) * [Heap]...
List D&C : Divide and Conquer H : Heap S : Sort G : Greedy BM : Bit Manipulation 圣: Stack 问: Queue D : Design GP : Graph 如何调试 main.swift是初始化Solution.func(val) ,然后就可以调试了。 确保在...
java lru leetcode leetcode Description My leetcode solutions. Statistics language num C++ 308 Python3 46 JavaScript 4 Java 2 SQL ...Sort ...Sort ...Sort ...Topological-Sort-拓扑排序 ...List 双向链表
List. Less than 5.02% of c++ online submissions for Sort List." 不太彳亍 大佬写的 找到了用python写的大佬,感觉方法似乎是一样的 03.23 03. Longest Substring Without Repeating Characters 使用数组进行直接...
leetcode走楼梯 LeetCoding My solutions for leetcode with explanations 【148.Sort List】 questions Sort a linked ...list. ...sortList(ListNode* head) { } }; Requirement: Sort a linked list i
最大公共字符串leetcode leetcode 数组 链表 二叉树 位操作 判断字符串的顺序排列 给定一个字符串数组,将字谜组合在一起。 例如,给定:["eat", "tea", "tan", "ate", "nat", "bat"], public class Solution { ...
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 ...
list.sort( key = lambda x: x[1] ) 图 = collections.defaultdict(list) heapq.heapify (列表) a = heapq.pop(队列) heapq.push(队列,ele) dq = collections.deque(list) append, appendleft, clear, copy...
leetcode 2 sum c LeetCode LeetCode 个人题解, 解法基于C++ Content Title Difficulty Solution ...sort ...List 20. Easy stack 21. Easy merge sort 22. Medium recursion、dfs 23. Hard heap sort
Arrays.sort(Object[])和Collections.sort(List)保证是稳定的。 如果需要部分排序,这对于保留原始排序很有用: 堆 对于Java,数据结构是PriorityQueue; 对于 Python,请参阅 heapq 中的函数 K 最小/最大元素来自:...
leetcode中325题python leetcode 以 参考 和 Hash相关 1_两数之和 387_字符串中的第一个唯一字符 链表操作 2 ...删除链表的倒数第N个节点 ...sort-list 234 回文链表 palindrome-linked-list 双指针遍历/滑动
leetcode 答案 leetcode Day 1 两数之和: 1。 考虑两层嵌套循环 2。...用dictionary以及 ...List[int], ...List[int]: ...List[int], ...List[int]: ...temp.sort() i=0 j=len(nums)-1 while i<j>target: j=j-1 elif (temp
Collections.sort(List,Comparator) 对列表进行排序 反向链表(给定链表反向部分的长度) ListNode start = pre.next; ListNode then = start.next; //key part of reversing given length linkedlist for(int i =...
List ArrayList和LinkedList的区别和删除时注意的点 7. Proxy 静态代理和动态代理 8. Reflection java 反射 9. Sort 多种排序方法 10. Sync synchronized 和 lock 的用法 11. Thread Thread创建、ThreadLocal用法、...
Sort & Search # Name Difficulty Solution index 1 直接插入 easy python :heart_suit: 2 简单选择排序 easy python :heart_suit: 3 冒泡排序 easy python :heart_suit: 4 希尔 easy python :heart_suit: 5 快排...
leetcode下载 Algorithm 记录一些很有意思的小代码.包括一些常见的面试题,及一些奇技淫巧. csy.array:数组相关 csy.backtracking:回溯法 八皇后 全排列 组合 csy.bbst: 红黑树 csy.binarytree:二叉树,包括插入 删除 ...
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-...