精华内容
下载资源
问答
  • 对链表排序

    千次阅读 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 ...
  • 利用快排单向链表排序

    千次阅读 2018-08-02 17:08:08
    利用快排单向链表进行排序,左右指针法和挖坑法都是不能使用的,因为这两种方法都要从最后往前进行查找,但是链表是双向的,往前面走是不可能的,所以只能采用前后指针法。 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)比较了两个节点的大小后,只交换数据域,而不改变指针,从而交换节点的顺序。 第二种办法比较简单,本文主要第...
  • 对链表进行排序

    2019-12-26 19:43:07
    对链表进行排序。 思路: 1.借助辅助列表list,将链表中的值压入到list。 2.list进行排序,将排好序的list中的值返回到链表里。 /** * Definition for singly-linked list. * struct ListNode { * int val...
  • 单向链表排序-归并排序

    千次阅读 2013-04-21 23:31:05
    链表排序中使用归并排序:归并排序不仅保持了它的 O( nlog(n) ) 的时间复杂度,而且它在数组排序中广受诟病的空间复杂度,在链表排序中从 O(n) 降低到 O( log(n) )。  对于单向链表的二路归并排序,首先是要找到...
  • 链表排序相对数组的排序更为复杂些,也是考察求职者是否真正理解了排序算法(而不是“死记硬背”) 链表的插入排序 public class LinkedInsertSort { static class ListNode { int val; ListNode next; ...
  • C++链表排序(归并法+快速排序)

    千次阅读 2021-04-18 22:16:34
    对链表归并排序的过程如下。 找到链表的中点,以中点为分界,将链表拆分成两个子链表。寻找链表的中点可以使用快慢指针的做法,快指针每次移动 2 步,慢指针每次移动 1步,当快指针到达链表末尾时,慢指针指向的链表...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 242,663
精华内容 97,065
关键字:

怎么对链表排序