- Java锁的逻辑(结合对象头和ObjectMonitor)
- 还在用饼状图?来瞧瞧这些炫酷的百分比可视化新图形(附代码实现)⛵
- 自动注册实体类到EntityFrameworkCore上下文,并适配ABP及ABPVNext
- 基于Sklearn机器学习代码实战
作者: Grey 。
原文地址:
博客园:单链表的排序问题 。
CSDN:单链表的排序问题 。
LeetCode 148. Sort List 。
将链表转换成数组,使用快速排序算法,然后把数组排序后的结果还原成链表.
时间复杂度 O(n*logn) ,空间复杂度 O(n) 。这个思路的核心就是快速排序算法,快速排序算法见如下博客 荷兰国旗问题与快速排序算法 说明,但是空间复杂度没有达到最优(最优解可以做到空间复杂度 O(1) ),完整代码如下:
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
int size = 0;
ListNode cur = head;
while (cur != null) {
size++;
cur = cur.next;
}
ListNode[] nodes = new ListNode[size];
cur = head;
int i = 0;
while (cur != null) {
nodes[i++] = cur;
cur = cur.next;
}
sortArr(nodes);
return arrToList(nodes);
}
private void sortArr(ListNode[] nodes) {
p(nodes, 0, nodes.length - 1);
}
private void p(ListNode[] arr, int L, int R) {
if (L >= R) {
return;
}
swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
int[] equalArea = netherlandsFlag(arr, L, R);
p(arr, L, equalArea[0] - 1);
p(arr, equalArea[1] + 1, R);
}
private int[] netherlandsFlag(ListNode[] nodes, int L, int R) {
if (L > R) {
return new int[]{-1, -1};
}
if (L == R) {
return new int[]{L, R};
}
int less = L - 1;
int more = R;
ListNode num = nodes[R];
for (int i = L; i < more; i++) {
if (nodes[i].val < num.val) {
swap(nodes, ++less, i);
} else if (nodes[i].val > num.val) {
swap(nodes, i--, --more);
}
}
swap(nodes, R, more);
return new int[]{less + 1, more};
}
public void swap(ListNode[] nodes, int i, int j) {
if (i != j) {
ListNode t = nodes[i];
nodes[i] = nodes[j];
nodes[j] = t;
}
}
public ListNode arrToList(ListNode[] nodes) {
ListNode head = nodes[0];
ListNode cur = head;
for (int i = 1; i < nodes.length; i++) {
cur.next = nodes[i];
cur = nodes[i];
}
cur.next = null;
return head;
}
}
本题可以利用归并排序算法,在时间复杂度同样为 O(n*logn) 的情况下,空间复杂度可以达到 O(1) ,本题参考了归并排序的迭代版本实现,归并排序算法的说明见如下博客 与归并排序相关的一些问题 .
归并排序的迭代方法,思路如下 。
设置一个步长,从 1 开始, 1,2,4,8,16……2^n 方式递增 。
每次处理对应步长的链表区间范围内的排序.
步长超过或者等于链表长度,则整个链表排序完成.
比如原始链表为: 1->3->4->2->5->6->4->6->8 。
先设置步长为 1,链表分成如下区间 。
[0……1] , [2……3] , [4……5] , [6……7] , [8……8] 。
注:最后一组不够分,则单独作为一组处理.
将如上区间内部排好序,得到的排序后的链表为 。
1->3 , 2->4 , 5->6 , 4->6 , 8 。
然后设置步长为 2,链表分成如下区间 。
[0……3] , [4……7] , [8……8] .
然后将上述区间内部先排好序,得到链表为 。
1->2->3->4 , 4->5->6->6 , 8 。
然后设置步长为 4,链表分成如下区间 。
[0……7] , [8……8] .
然后将上述区间内部先排好序,得到链表为 。
1->2->3->4->4->5->6->6 , 8 。
最后设置步长为 8,链表只有一个区间,直接排序,得到最后结果 。
1->2->3->4->4->5->6->6->8 。
完整代码如下 。
class Solution {
public ListNode sortList(ListNode head) {
int N = 0;
ListNode cur = head;
while (cur != null) {
N++;
cur = cur.next;
}
ListNode h = head;
ListNode teamFirst = head;
ListNode pre = null;
int L = 1;
while (L < N) {
while (teamFirst != null) {
ListNode[] hthtn = hthtn(teamFirst, L);
ListNode[] mhmt = merge(hthtn[0], hthtn[1], hthtn[2], hthtn[3]);
if (h == teamFirst) {
h = mhmt[0];
pre = mhmt[1];
} else {
pre.next = mhmt[0];
pre = mhmt[1];
}
teamFirst = hthtn[4];
}
teamFirst = h;
pre = null;
L <<= 1;
}
return h;
}
public ListNode[] hthtn(ListNode teamFirst, int len) {
ListNode ls = teamFirst;
ListNode le = teamFirst;
ListNode rs = null;
ListNode re = null;
ListNode next = null;
int p = 0;
while (teamFirst != null) {
// 之所以这里是小于等于,是因为这里可能不满足分组的个数(不足个数)
if (p <= len - 1) {
le = teamFirst;
}
if (p == len) {
rs = teamFirst;
}
if (p > len - 1) {
re = teamFirst;
}
if (p == (len << 1) - 1) {
break;
}
p++;
teamFirst = teamFirst.next;
}
if (le != null) {
le.next = null;
}
if (re != null) {
next = re.next;
re.next = null;
}
return new ListNode[]{ls, le, rs, re, next};
}
// 返回merge后的头和尾
// 注意边界考虑
public ListNode[] merge(ListNode h1, ListNode t1, ListNode h2, ListNode t2) {
if (h2 == null) {
return new ListNode[]{h1, t1};
}
ListNode head = h1;
ListNode tail = h1;
ListNode c = null;
ListNode pre = null;
while (h1 != t1.next && h2 != t2.next) {
if (h1.val > h2.val) {
c = h2;
h2 = h2.next;
} else {
c = h1;
h1 = h1.next;
}
if (pre == null) {
// 设置merge后的头节点,赋值给head
// 后续就由pre去往下插入节点
pre = c;
head = c;
} else {
pre.next = c;
pre = c;
}
}
// h1节点没越界
if (h1 != t1.next) {
while (h1 != t1.next) {
pre.next = h1;
pre = pre.next;
tail = h1;
h1 = h1.next;
}
} else {
while (h2 != t2.next) {
pre.next = h2;
pre = pre.next;
tail = h2;
h2 = h2.next;
}
}
return new ListNode[]{head, tail};
}
}
算法和数据结构笔记 。
最后此篇关于单链表的排序问题的文章就讲到这里了,如果你想了解更多关于单链表的排序问题的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
我创建了一个单链表。一切正常。 我只想知道我是否在我的代码中做了任何有潜在危险的事情。我关心的代码片段是我的推送、弹出和清理。部分代码仅用于用户交互,因此并不重要(无论如何我都发布了它,以便更清楚地了
链表:是一个有序的列表,但是它在内存中是分散存储的,使用链表可以解决类似约瑟夫问题,排序问题,搜索问题,广义表 单向链表,双向链表,环形链表 PHP的底层是C,当一个程序运行时,内存分成五个区(
我最近开始专注于使用数据结构及其用例的编码练习。下面是我的程序,将数据插入到单个链表中,其中每个节点存储下一个节点的对象。这个程序运行良好。我想了解下面的代码有多有效,所遵循的逻辑是否有效且高效。当节
尝试编写一种方法,从单链表中删除某个值的所有实例,但它似乎不起作用。 我试图适应头部是否包含该值,但我不确定这是否是正确的方法: public void remove (int value) {
struct nodeStruct { int value; struct nodeStruct *next; } struct nodeStruct* List_createNode
typedef struct node { int data; struct node *next; } NODE; NODE* add_head(NODE **phead, int data) {
void addToEnd() { newnode = (struct node*)malloc(sizeof(struct node)); printf ("Enter the cu
我想编写一种方法,从单向链表中删除具有重复数据值的连续项。该方法应返回移除的项目数。该方法应根据需要清理内存,并应假定内存是使用 new 分配的。 比如传入列表 ->a->b->c->c->a->b-
我有一个存储播放列表的表。它的定义非常简单,只有三列: setID - 引用播放列表中的一行的 16 位十六进制 songID - 16 位十六进制数,引用我的歌曲表中的一行 nextID - 16
为什么我的代码不删除链表的最后一个元素?我创建了一个当前指针来横向穿过我的列表并跳出循环..(下一个是我的结构中名为 Card_Node 的点)。回答起来应该很简单,只是不确定为什么它不会删除列表中的
大家好,我现在正在为期中考试学习,正在努力尝试使用单链表创建一个简单的程序。我想让它做的就是将“1”、“2”、“3”、“4”插入列表并打印出来。请看下面的代码: #include #include
我想创建单链表(使用类),其中每个列表中都有:指向文本的指针、整数、指向下一个列表的指针。 我需要实现 3 个功能:插入(将列表插入单链表并根据指针指向的文本使用strcmp对元素进行排序)remov
我已经实现了一个单链表,我注意到了非常奇怪的行为,但无法查明它发生的确切原因。我已经尝试使用 gdb 找出问题所在,看起来每当我计算列表的大小时,事情就开始出错了。这是我用来测试我的实现的程序,下面是
我正在尝试找出一种从链表中间删除的算法.. 我的想法是遍历链表,找到我要删除的节点之前的节点,命名为Nprev,将Nprev设置为Nnext,其中Nnext在要删除的节点之后Ndelete。 所以 N
我正在尝试创建一个简单的单向链表。以前,我成功地做到了这一点,没有任何错误,但是现在我遇到了错误。我怀疑由于第 23 行中的 if 语句,内存分配存在某种问题。 我尝试过的: 我在我的所有声明中都使用
我正在尝试创建一个简单的单向链表。以前,我成功地做到了这一点,没有任何错误,但是现在我遇到了错误。我怀疑由于第 23 行中的 if 语句,内存分配存在某种问题。 我尝试过的: 我在我的所有声明中都使用
我在学习C++语言的同时尝试构建一个链表,并实现一个从最低到最高的节点插入功能。我遵循了互联网和教科书中的一些教程。 我有一个用于链表节点设置的结构: struct Node { private:
本文实例讲述了Python数据结构与算法之链表定义与用法。分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表
1561/1563 test cases passed 问题描述: You are given two non-empty linked lists representing two non-nega
我有一个任务来实现一个单链表。我试图找出如何获取头部,但最终出现堆栈溢出错误或空指针错误。有人可以帮助我吗?我已经显示了相关的代码片段: public class Llist { privat
我是一名优秀的程序员,十分优秀!