Leetcode#148 Sort List
2024-08-23 21:17:46
链表归并排序
真是恶心的一道题啊,哇了好多次才过。
代码:
void mergeList(ListNode *a, ListNode *b, ListNode *&h, ListNode *&t) {
h = t = NULL;
while (a && b) {
ListNode *c = NULL;
if (a->val <= b->val) {
c = a;
a = a->next;
}
else {
c = b;
b = b->next;
}
if (!h)
h = t = c;
else {
t->next = c;
t = t->next;
}
}
while (a) {
t->next = a;
t = t->next;
a = a->next;
}
while (b) {
t->next = b;
t = t->next;
b = b->next;
}
} ListNode *sortList(ListNode *head) {
ListNode *prev = NULL;
ListNode *h1 = NULL;
ListNode *h2 = NULL;
ListNode *t1 = NULL;
ListNode *t2 = NULL;
ListNode *node = NULL;
int len = ; node = head;
while (node && (++len))
node = node->next; for (int l = ; l < len; l <<= ) {
prev = NULL;
h1 = NULL;
h2 = NULL;
t1 = NULL;
t2 = NULL;
node = head; while (node) {
h1 = t1 = node;
for (int i = ; node && i < l; i++) {
t1 = node;
node = node->next;
}
if (t1)
t1->next = NULL;
h2 = t2 = node;
for (int i = ; node && i < l; i++) {
t2 = node;
node = node->next;
}
if (t2)
t2->next = NULL; ListNode *h, *t;
if (h2)
mergeList(h1, h2, h, t);
else {
h = h1;
t = t1;
}
if (!prev)
head = h;
else
prev->next = h;
t->next = node;
prev = t;
}
} return head;
}
最新文章
- 双向链表、双向循环链表的JS实现
- listview 模仿用户点击事件。
- java中的hashcode()和equals()
- c/c++面试题(6)运算符重载详解
- 用户管理 之 用户(User)和用户组(Group)配置文件详解
- linux笔记:linux系统安装-linux系统安装
- 直接取HANA数据库数据,动态QUERY
- Eclipse的java代码出错:The import org.apache cannot be resolved
- Unity3D知识点
- Python设计模式——建造者模式
- 使用Dreamwaver cc中的SVN功能,用于传输BAE和SAE中的文件
- ADO.net基础学习总结
- 密码学——网间数据加密传输全流程(SSL加密原理)
- hadoop2.6.0实践:引入开发依赖的jar包
- APP测试要点—UI、功能测试
- 删除PeopleSoft Process Scheduler服务器定义
- CSS,JavaScript知识点
- python数据类型一:字符串
- 剑指offer——从上往下打印二叉树
- java IO流之详细总结