【LeetCode】148. Sort List 解题报告(Python & C++)
2024-09-08 14:03:42
作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/
题目地址:https://leetcode.com/problems/sort-list/description/
题目描述
Sort a linked list in O(n log n) time using constant space complexity.
Example 1:
Input: 4->2->1->3
Output: 1->2->3->4
Example 2:
Input: -1->5->3->4->0
Output: -1->0->3->4->5
题目大意
把单链表进行排序。
解题方法
这个题要求用O(nlongn)的时间复杂度和O(1)的空间复杂度。所以可以使用merge排序,但是如果是链表可以修改指针,把两个有序链表进行原地的合并。
Merge排序就是先划分成一前一后等分的两块,然后对两块分别进行排序,然后再合并两个有序序列。
第一步,如何等分地划分,可以使用快慢指针的方式,当快指针到达结尾,那么慢指针到了中间位置,把链表进行截断分成了两个。
第二步,合并有序的序列,对于单链表来说,正好用到了Merge Two Sorted Lists里的把两个链表合并的方法。
事实上,这个答案里面并不是O(1)的空间,因为,第一,添加了新的链表头的个数会随着递归的次数而不断增加,并不是常量个;第二,递归本身就不是常量空间。
Python代码如下:
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next: return head
pre, slow, fast = head, head, head
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None
l1 = self.sortList(head)
l2 = self.sortList(slow)
return self.mergeTwoLists(l1, l2)
def mergeTwoLists(self, l1, l2):
head = ListNode(0)
move = head
if not l1: return l2
if not l2: return l1
while l1 and l2:
if l1.val < l2.val:
move.next = l1
l1 = l1.next
else:
move.next = l2
l2 = l2.next
move = move.next
move.next = l1 if l1 else l2
return head.next
C++代码如下,对于链表操作全是指针操作,真的很烦:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// make the list sort.
ListNode* sortList(ListNode* head) {
if (!head || !head->next) return head;
ListNode* fast = head;
ListNode* slow = head;
ListNode* pre = head;
while (fast && fast->next) {
pre = slow;
fast = fast->next->next;
slow = slow->next;
}
pre->next = nullptr;
ListNode* l1 = sortList(head);
ListNode* l2 = sortList(slow);
return mergeList(l1, l2);
}
// merge two sort list.
ListNode* mergeList(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1) cur->next = l1;
else cur->next = l2;
return dummy->next;
}
};
日期
2018 年 3 月 20 日 —— 阳光明媚~
2019 年 1 月 11 日 —— 小光棍节?
最新文章
- 纯CSS3实现的一些酷炫效果
- freemarker种种
- MVC POST在ACTION上进行多个模型的数据绑定
- 【Win10 应用开发】人脸识别
- python成长之路【第十四篇】:HTML初步认识
- Oracle锁的机制
- python os.path模块常用方法详解:转:http://wangwei007.blog.51cto.com/68019/1104940
- 对discuz的代码分析学习(四)论坛入口文件
- PDF417码制尺寸定义
- c/c++数组名和指针区别深入探索
- Java面试题大全
- HTML 基础学习笔记
- Java历程-初学篇 Day02变量,数据类型和运算符
- BZOJ4944 泳池 解题报告
- 分享关于搭建高性能WEB服务器的一篇文章
- Divisor Subtraction
- struts1.x 核心控制器 和 用户自定义控制器扩展类;
- [转]JS根据useAgent来判断edge, ie, firefox, chrome, opera, safari 等浏览器的类型及版本
- UI5-文档-4.12-Shell Control as Container
- adb端口占用及模拟器调试