• ## 对链表排序

千次阅读 2014-09-02 21:24:40
对链表排序：https://oj.leetcode.com/problems/sort-list/ 看到链表排序，第一反应无外乎就是希尔排序、基数排序和桶排序。想了想最好写的是基数排序，源码如下： public class Main { public static ...
要开始找工作，又挨了顿骂，这事不爽，刷一个LeetCode开心一下。
对链表排序：https://oj.leetcode.com/problems/sort-list/
看到链表排序，第一反应无外乎就是希尔排序、基数排序和桶排序。想了想最好写的是基数排序，源码如下：

public class Main {

public static void main(String[] args) {
int[] data = { -84, 142, 41, -17, -71, 170, 186, 183, -21, -76, 76, 10,
29, 81, 112, -39, -6, -43, 58, 41, 111, 33, 69, 97, -38, 82,
-44, -7, 99, 135, 42, 150, 149, -21, -30, 164, 153, 92, 180,
-61, 99, -81, 147, 109, 34, 98, 14, 178, 105, 5, 43, 46, 40,
-37, 23, 16, 123, -53, 34, 192, -73, 94, 39, 96, 115, 88, -31,
-96, 106, 131, 64, 189, -91, -34, -56, -22, 105, 104, 22, -31,
-43, 90, 96, 65, -85, 184, 85, 90, 118, 152, -31, 161, 22, 104,
-85, 160, 120, -31, 144, 115 };
ListNode head = new ListNode(data[0]);
ListNode now = head;
for (int i = 1; i < data.length; ++i) {
now.next = new ListNode(data[i]);
now = now.next;
}
sortList(head);
}

static class ListNode {
int val;
ListNode next;

ListNode(int x) {
val = x;
next = null;
}
}

public static ListNode sortList(ListNode head) {
// radix
final int RADIX = 10;
// positive numbers
ListNode[] positiveHeads = new ListNode[RADIX];
ListNode[] positiveTails = new ListNode[RADIX];
// negative
ListNode[] negativeHeads = new ListNode[RADIX];
ListNode[] negativeTails = new ListNode[RADIX];
// radix
int offset = 1;
// longest number
boolean maxInitialed = false;
int max = 0;
// continue sort on next digit
boolean goNext = true;
while (goNext) {
// reset for next radix digit
ListNode now = head;
positiveHeads = new ListNode[RADIX];
positiveTails = new ListNode[RADIX];
negativeHeads = new ListNode[RADIX];
negativeTails = new ListNode[RADIX];
// iterate list
while (null != now) {
// initialize longest value
if (!maxInitialed) {
if (Math.abs(now.val) > max) {
max = Math.abs(now.val);
}
}
// hash to a radix container
int index = (now.val / offset) % RADIX;
if (now.val >= 0) {
// positive
if (null == positiveHeads[index]) {
positiveHeads[index] = now;
positiveTails[index] = now;
} else {
positiveTails[index].next = now;
positiveTails[index] = now;
}

now = now.next;
positiveTails[index].next = null;
} else {
// negative
index = -index;
if (null == negativeHeads[index]) {
negativeHeads[index] = now;
negativeTails[index] = now;
} else {
negativeTails[index].next = now;
negativeTails[index] = now;
}

now = now.next;
negativeTails[index].next = null;
}
}
// merge list
head = null;
ListNode tail = null;
// negative should be merged from 9 to 0
for (int i = RADIX - 1; i >= 0; --i) {
if (null == negativeHeads[i]) {
continue;
}
if (null == head) {
head = negativeHeads[i];
} else {
tail.next = negativeHeads[i];
}
tail = negativeTails[i];
}
// positive merged from 0 to 9
for (int i = 0; i < RADIX; ++i) {
if (null == positiveHeads[i]) {
continue;
}
if (null == head) {
head = positiveHeads[i];
} else {
tail.next = positiveHeads[i];
}
tail = positiveTails[i];
}
// initialized after one iteration
maxInitialed = true;
// next digit
offset *= RADIX;
// if no more big number to sort
goNext = offset < max;
}
return head;
}
}

展开全文
• leetcode解题之148. Sort List Java版（对链表排序
148. Sort List

Sort a linked list in O(n log
n) time using constant space complexity.
在O(nlogn)时间内，使用常数空间对链表进行排序。使用归并排序
参考：
归并排序 原理及其java实现
21.Merge Two Sorted Lists Java版 递归和非递归实现
23.Merge k Sorted Lists Java版本（合并k个有序的链表）
	public ListNode sortList(ListNode head) {
if (head == null || head.next == null)
return head;
// 使用快慢指针查找中间结点
ListNode fast = head;
ListNode slow = head;
while (fast.next != null) {
fast = fast.next.next;
// 让slow少走一步，结点数目均匀
if (fast == null)
break;
slow = slow.next;
}
ListNode right = slow.next;
// 注意断链
slow.next = null;

ListNode left = sortList(head);
right = sortList(right);
return mergeTwoLists(left, right);
}
// 递归实现链表排序
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode res = null;
if (l1 == null)
return l2;
if (l2 == null)
return l1;
if (l1.val <= l2.val) {
res = l1;
l1.next = mergeTwoLists(l1.next, l2);
} else {
res = l2;
l2.next = mergeTwoLists(l1, l2.next);
}
return res;
}


展开全文
• 考虑归并排序:  1 找出链表的中间节点，用快慢... 2 递归左右子链表排序  3 合并俩个子链表 ListNode *sortList(ListNode *head) { if(head==NULL || head->next==NULL){ return head; } ListNode* middl
考虑归并排序:
1 找出链表的中间节点，用快慢指针。
2 递归对左右子链表排序
3 合并俩个子链表
    ListNode *sortList(ListNode *head) {
if(head==NULL || head->next==NULL){
return head;
}
ListNode* middle=findMiddle(head);
ListNode* right=sortList(middle->next);
middle->next=NULL;
ListNode* left=sortList(head);
return mergeList(left,right);
}
ListNode* findMiddle(ListNode* root){
//用快慢指针
ListNode* fast=root->next;
ListNode* slow=root;
while(slow!=NULL&&fast->next!=NULL){
slow=slow->next;
fast=fast->next->next;
}
return slow;
}
ListNode* mergeList(ListNode* root1,ListNode* root2){
if(root1==NULL)
return root2;
if(root2==NULL)
return root1;
ListNode* pHead=new ListNode(0);
ListNode* p=pHead;
while(root1!=NULL&&root2!=NULL){
if(root1->val<root2->val){
p->next=root1;
root1=root1->next;
}else{
p->next=root2;
root2=root2->next;
}
p=p->next;
}
if(root1 != NULL)
p->next=root1;
if(root2 != NULL)
p->next=root2;
ListNode* head=pHead->next;
delete pHead;
pHead=NULL;
return head;
}
展开全文
• 题目描述：建立一个链表，其每个节点代表一位学生的信息。信息从文件student.in中读取(文件student.in是外部已经存在文件，其格式为...以姓名为标准按照字母表顺序对链表进行排序，输出排序后的学生姓名和学号 题目...
题目描述：建立一个链表，其每个节点代表一位学生的信息。信息从文件student.in中读取(文件student.in是外部已经存在文件，其格式为第一行是一个大于零的整数表示学生数量，以后每行表示一位学生的信息分别有学号、姓名、性别、年龄)。

要求：1. 求所有学生的平均年龄

2. 以姓名为标准按照字母表顺序对链表进行排序，输出排序后的学生姓名和学号

题目分析：本题主要考察c语言中的文件读写信息、链表创建和链表排序。

先介绍一下c语言中对文件操作的函数  ：

(1)c语言中打开文件函数fopen(文件名，使用文件方式），关闭文件fclose(文件指针)，其中文件读写方式主要                          ①"r"只 读 ②"w"只写，如果指定文件不存在建立新文件③"r+"读写④"w+"读写，如果指定文件不存在建立新文件。

(2)c语言中读写字符所用函数fgetc(fp)从fp所指向的文件读入一个字符；fputc(ch,fp)把字符ch写到文件指针变量fp所指              向的文件中

(3)其次C语言读写字符串所用函数fets(str,n,fp)从fp指向的文件读入一个长度为n-1的字符串，存放到字符数组str中；                 fputs(str,fp)把str所指向的字符串写到文件指针变量fp所指向的文件中。

本题解决思路：先把文件student.in中的信息读出，然后用这些信息建立学生链表(StuLink)。链表创建完成后，完成要求               1：遍历链表找出每个学生的年龄，然后求平均年龄。完成要求二 ：利用选择排序思想对学生姓名按字母表顺序进行链表              排序，然后输出排序好的姓名和学号。

一、已经存在的文件student.in信息

本文件我将它放在桌面具体路径为C:\Users\Mr.w\Desktop\student.in,以便在读入文件信息时快速找到此文件

二、读入文件信息并创建链表

部分代码：


typedef struct Student{
int num;    //学号
char name[20]; //姓名
char sex[2];     //性别
int age;    //年龄

struct Student *next;
}Student,*StuLink;

fp = fopen("C:\\Users\\Mr.w\\Desktop\\student.in", "r");//在指定位置读取信息
fgets(ch,4,fp);    //读取信息
q = (StuLink)malloc(sizeof(Student));   //创建单个学生结点
fgets(q->name, 5, fp);  //将读取到的学生姓名赋予当前学生结点的name域

三、求平均年龄

void ageAverage(StuLink s){
StuLink p=s->next;
int sum = 0, count = 0;
double aver;
while (p!=NULL)
{
sum += p->age;
count++;
p = p->next;
}
aver =(double) sum / count;
printf("平均分:%.2f\n", aver);
}

四、对学生姓名按字母表顺序排序

void nameSort(StuLink s){
StuLink minpre, min, p, pre,r;
r = s;
while (r->next != NULL){  //选择排序对链表按名字排序
pre = r;
p = pre->next;
min = p;
minpre = pre;
while (p != NULL)
{
if (strcmp(min->name,p->name) > 0){
minpre = pre;
min = p;
}
pre = p;
p = p->next;
}
if (r->next == min)
r = r->next;
else{
minpre->next = min->next;  //防止断链
min->next = r->next;    //尾插法
r->next = min;
r = min;

}

}
r = s->next;
while (r!=NULL)
{
printf("%s %d\n", r->name,r->num);
r = r->next;
}

}

运行结果：

对本问题有什么疑问欢迎讨论！！！


展开全文
• ## 链表排序

千次阅读 2015-09-27 19:08:19
这里的链表排序其实比较简单， 就是从原链表中取出链首节点， 按照排序规则（从小到大）插入到新的链表中。 最后将链表的头指针指向新链表的头指针。 源代码： ListNode.h void Sort(); // 排序（从小到大） ...
• ## 链表排序算法

万次阅读 多人点赞 2018-04-18 10:34:09
排序算法概述盗个图转自：https://www.cnblogs.com/onepixel/articles/7674659.html排序算法复杂度由于是链表排序，首先定义链表节点数据结构common.htypedef struct Node LNode; struct Node { int data; LNode ...
• 基于冒泡排序的链表排序 O(n²) 比较： 基于冒泡排序的链表排序，易懂，运行效率不高 基于归并排序的链表排序，效率高 LinkNode.java LinkedListBobbleSort.java package cn.stu.test; public class ...
• 利用快排单向链表进行排序，左右指针法和挖坑法都是不能使用的，因为这两种方法都要从最后往前进行查找，但是链表是双向的，往前面走是不可能的，所以只能采用前后指针法。 struct ListNode { int _val; ...
• ## 双向链表排序

万次阅读 2018-07-17 20:52:18
双向链表的结构体，包括一个前驱节点的指针、一个后继节点的指针以及一个存储数据的data域，initList函数初始化单节点的双链表，addList函数采用头插入方法添加一个节点到双链表中，sort函数实现了链表排序，...
• ## 无序链表排序

千次阅读 2016-05-20 09:45:11
分析链表排序比较特殊，由于不连续的性质，所以在进行排序的时候要引入外排思想，因此归并排序或者多路归并就成为了排序的选择。 归并排序分为拆分、合并两个阶段： 1. 拆分 需要拆分出链表中间节点，并赋值NULL...
• ## 链表插入排序

千次阅读 2016-04-26 22:11:16
题目描述：用插入排序对链表排序 样例：Given 1->3->2->0->null, return 0->1->2->3->null 之前，在我的博文“将排序链表转换为二分查找树”（详见：点击打开链接）中已经介绍了链表的快慢指针法，以及“摘链”...
• 在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。 示例 1: 输入: 4-&gt;2-&gt;1-&gt;3 输出: 1-&gt;2-&gt;3-&gt;4 示例 2: 输入: -1-&gt;5-&gt;3-&...
• 1. 对链表进行插入排序（力扣：147） 2. 排序链表（力扣：148） Java实现
• 对链表排序有两种方法： （1）比较了两个节点的大小后，指针进行改变，从而交换节点的顺序； （2）比较了两个节点的大小后，只交换数据域，而不改变指针，从而交换节点的顺序。 第二种办法比较简单，本文主要第...
• 对链表进行排序。 思路： 1.借助辅助列表list，将链表中的值压入到list。 2.list进行排序，将排好序的list中的值返回到链表里。 /** * Definition for singly-linked list. * struct ListNode { * int val...
• 链表排序中使用归并排序：归并排序不仅保持了它的 O( nlog(n) ) 的时间复杂度，而且它在数组排序中广受诟病的空间复杂度，在链表排序中从 O(n) 降低到 O( log(n) )。  对于单向链表的二路归并排序，首先是要找到...
• 链表排序相对数组的排序更为复杂些，也是考察求职者是否真正理解了排序算法（而不是“死记硬背”） 链表的插入排序 public class LinkedInsertSort { static class ListNode { int val; ListNode next; ...
• 对链表归并排序的过程如下。 找到链表的中点，以中点为分界，将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法，快指针每次移动 2 步，慢指针每次移动 1步，当快指针到达链表末尾时，慢指针指向的链表...

...