精华内容
下载资源
问答
  • 对链表进行相应操作 链表为双向链表 其中的操作有 快速排序 选择排序 插入 删除链表 从链表中获取一个数等等 程序并没有测试周全 欢迎下载 若发现问题希望在我CSDN留言 以便及时更改
  • 根据题目要求,我们需要在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。 所以我们选择的是二路归并排序 /* 由于题目要求空间复杂度是 O(1),因此不能使用递归。因此这里使用 bottom-to-up 的算法来...

    根据题目要求,我们需要在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。
    所以我们选择的是二路归并排序

    /*
    由于题目要求空间复杂度是 O(1),因此不能使用递归。因此这里使用 bottom-to-up 的算法来解决。
    bottom-to-up 的归并思路是这样的:先两个两个的 merge,完成一趟后,再 4 个4个的 merge,直到结束。
    举个简单的例子:[4,3,1,7,8,9,2,11,5,6].
    step=1: (3->4)->(1->7)->(8->9)->(2->11)->(5->6)
    step=2: (1->3->4->7)->(2->8->9->11)->(5->6)
    step=4: (1->2->3->4->7->8->9->11)->5->6
    step=8: (1->2->3->4->5->6->7->8->9->11)

    链表里操作最难掌握的应该就是各种断链啊,然后再挂接啊。在这里,我们主要用到链表操作的两个技术:
    merge(l1, l2),双路归并,我相信这个操作大家已经非常熟练的,就不做介绍了。
    cut(l, n),可能有些同学没有听说过,它其实就是一种 split 操作,即断链操作。不过我感觉使用 cut 更准确一些,它表示,将链表 l 切掉前 n 个节点,并返回后半部分的链表头。
    额外再补充一个 dummyHead 大法,已经讲过无数次了,仔细体会吧。

    希望同学们能把双路归并和 cut 断链的代码烂记于心,以后看到类似的题目能够刷到手软。
    掌握了这三大神器后,我们的 bottom-to-up 算法代码就十分清晰了:
    */

    class Solution {
    public:
        ListNode* sortList(ListNode* head) {
            ListNode dummyHead(0);
            dummyHead.next = head;
            auto p = head;
            int length = 0;
            while (p) {
                ++length;
                p = p->next;
            }
            
            for (int size = 1; size < length; size <<= 1) {
                auto cur = dummyHead.next;
                auto tail = &dummyHead;
                
                while (cur) {
                    auto left = cur;
                    auto right = cut(left, size); //剪切
                    cur = cut(right, size); //剪切
                    
                    tail->next = merge(left, right);	//二路归并
                    while (tail->next) {
                        tail = tail->next;
                    }
                }
            }
            return dummyHead.next;
        }
        
        ListNode* cut(ListNode* head, int n) {
            auto p = head;
            while (--n && p) {
                p = p->next;
            }
            
            if (!p)
                return nullptr;
            
            auto next = p->next;
            p->next = nullptr;
            return next;
        }
        
        ListNode* merge(ListNode* l1, ListNode* l2) {
            ListNode dummyHead(0);
            auto p = &dummyHead;
            while (l1 && l2) {
                if (l1->val < l2->val) {
                    p->next = l1;
                    p = l1;
                    l1 = l1->next;       
                }
                else {
                    p->next = l2;
                    p = l2;
                    l2 = l2->next;
                }
            }
            p->next = l1 ? l1 : l2;
            return dummyHead.next;
        }
    };
    
    展开全文
  • 链表选择排序

    2011-07-22 21:32:33
    对链表进行选择排序的函数为:view plain/* ========================== 功能:选择排序(由小到大) 返回:指向链表表头的指针 ========================== */ struct student *SelectSort
     对链表进行选择排序的函数为:
    1. /* 
    2. ========================== 
    3.  功能:选择排序(由小到大) 
    4.  返回:指向链表表头的指针 
    5. ========================== 
    6. */  
    7. struct student *SelectSort (struct student *head)  
    8. {  
    9.     struct student *first;     //排列后有序链的表头指针  
    10.     struct student *tail;      //排列后有序链的表尾指针  
    11.     struct student *p_min;     //保留键值更小的节点的前驱节点的指针  
    12.     struct student *min;       //存储最小节点  
    13.     struct student *p;         //当前比较的节点  
    14.   
    15.     first = NULL;  
    16.     while(head != NULL)       //在链表中找键值最小的节点  
    17.     {  
    18.         //注意:这里for语句就是体现选择排序思想的地方  
    19.         for (p = head, min = head; p->next != NULL; p = p->next)  //循环遍历链表中的节点,找出此时最小的节点  
    20.         {  
    21.             if (p->next->num < min->num)     //找到一个比当前min小的节点  
    22.             {  
    23.                 p_min = p;        //保存找到节点的前驱节点:显然p->next的前驱节点是p  
    24.                 min = p->next;     //保存键值更小的节点  
    25.             }  
    26.         }  
    27.   
    28.         //上面for语句结束后,就要做两件事;一是把它放入有序链表中;二是根据相应的条件判断,安排它离开原来的链表  
    29.   
    30.         //第一件事  
    31.         if (first == NULL)     //如果有序链表目前还是一个空链表  
    32.         {  
    33.             first = min;        //第一次找到键值最小的节点  
    34.             tail = min;        //注意:尾指针让它指向最后的一个节点  
    35.         }  
    36.         else              //有序链表中已经有节点  
    37.         {  
    38.             tail->next = min;    //把刚找到的最小节点放到最后,即让尾指针的next指向它  
    39.             tail = min;           //尾指针也要指向它  
    40.         }  
    41.   
    42.         //第二件事  
    43.         if (min == head)            //如果找到的最小节点就是第一个节点  
    44.         {  
    45.             head = head->next;      //显然让head指向原head->next,即第二个节点,就OK  
    46.         }  
    47.         else            //如果不是第一个节点  
    48.         {  
    49.             p_min->next = min->next;  //前次最小节点的next指向当前min的next,这样就让min离开了原链表  
    50.         }  
    51.     }  
    52.   
    53.     if (first != NULL)      //循环结束得到有序链表first  
    54.     {  
    55.         tail->next = NULL;   //单向链表的最后一个节点的next应该指向NULL  
    56.     }  
    57.     head = first;  
    58.     return head;  


    展开全文
  • 对链表进行插入排序 插入排序算法: 插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。 每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并...

    题目

    1. 对链表进行插入排序
      插入排序算法:

    插入排序是迭代的,每次只移动一个元素,直到所有元素可以形成一个有序的输出列表。
    每次迭代中,插入排序只从输入数据中移除一个待排序的元素,找到它在序列中适当的位置,并将其插入。
    重复直到所有输入数据插入完为止。

    示例 1:
    在这里插入图片描述
    输入: 4->2->1->3
    输出: 1->2->3->4

    解析

    排序并不陌生,数组可以用冒泡和选择排序法。
    排序过程
    对于无序单链表,需要将链表拆分,比较。重组形成有序链表。
    我们可以采用将头节点取下来,作为新有序链表的头(realhead);
    next指向原链表的第二个节点,每完成一次插入排序,next向后走一步,
    直到next等于NULL,排序完毕。
    插入方式
    小于头节点则头插,头插后后定义新头。
    同时记录尾节点(tail),大于尾节点则尾插,尾插后定义新尾巴。
    都不满足则为中间(2~n)插入,单链表的中间插入需要记录当前位置和上一个位置的地址,否则会丢失无法链接在一起。用cur和curprev寻找合适的插入位置,next->val小于cur->val时满足插入条件,不满足同时移动一步。
    每次中间插入完成后将cur和curprev重新定义,cur是有序链表第二个节点,curprev是有序链表第一个节点。

    图解

    在这里插入图片描述

    源代码以及调试应用场景代码

    #include<Windows.h>
    #include<stdio.h>
    #include <assert.h>
    #pragma warning (disable:4996)
    struct ListNode {
       int val;
       struct ListNode *next;
    };
    typedef struct ListNode ListNode;
    struct ListNode* insertionSortList(struct ListNode* head){
    	if (head == NULL)
    	{
    		return NULL;
    	}
    	ListNode* cur = head;
    	ListNode*curprev = NULL;
    	ListNode* next = head->next;
    	cur->next = NULL;
    	ListNode* realhead = head;
    	ListNode* tail = head;
    	while (next)
    	{
    		//头插
    		if (next->val <= realhead->val)
    		{
    			ListNode*temp = next->next;
    			next->next = realhead;
    			realhead = next;
    			next = temp;
    			curprev = realhead;
    			cur = curprev->next;
    		}
    		//尾插
    		else if (next->val>tail->val)
    		{
    			tail->next = next;
    			tail = next;
    			ListNode*temp = next->next;
    			next->next = NULL;
    			next = temp;
    		}
    		else
    			//中间插
    		{
    			while (next->val > cur->val)
    			{
    				curprev = cur;
    				cur = cur->next;
    			}
    			if (next->val <= cur->val)
    			{
    				ListNode*temp = next->next;
    				next->next = cur;
    				curprev->next = next;
    				next = temp;
    				cur = realhead->next;
    				curprev = realhead;
    			}
    		}
    	}
    	return realhead;
    }
    int main()
    {
    	ListNode*n6 = (ListNode*)malloc(sizeof(ListNode));
    	if (n6)
    	{
    		n6->val = 35;
    		n6->next =NULL;		
    	}
    	ListNode*n5 = (ListNode*)malloc(sizeof(ListNode));
    	if (n5)
    	{
    		n5->val = 53;
    		n5->next = n6;
    
    	}
    	ListNode*n4 = (ListNode*)malloc(sizeof(ListNode));
    	if (n4)
    	{
    		n4->val = -24;
    		n4->next = n5;
    	
    	}
    	ListNode*n3 = (ListNode*)malloc(sizeof(ListNode));
    	if (n3)
    	{
    		n3->val = 133;
    		n3->next = n4;
    
    	}
    	ListNode*n2 = (ListNode*)malloc(sizeof(ListNode));
    	if (n2)
    	{
    		n2->val = 220;
    		n2->next = n3;
    
    	}
    	ListNode*head = (ListNode*)malloc(sizeof(ListNode));
    	if (head)
    	{
    		head->val = 999;
    		head->next = n2;
    	
    	}
    	ListNode* list = head;
    	while (head)
    	{
    		printf("%10d->", head->val);
    		head = head->next;
    	}
    	printf("NULL\n");
    	head = list;
    	while (head)
    	{
    		printf("%10p->", head);
    		head = head->next;
    	}
    	printf("NULL\n");
    	head = list;
    	ListNode* sortNode = insertionSortList(head);
    	ListNode* cpylist = sortNode;
    	while (sortNode)
    	{
    		printf("%10d->", sortNode->val);
    		sortNode = sortNode->next;
    	}
    	printf("NULL\n");
    	sortNode = cpylist;
    	while (sortNode)
    	{
    		printf("%10p->", sortNode);
    		sortNode = sortNode->next;
    	}
    	printf("NULL\n");
    	system("pause");
    }
    
    展开全文
  • 归并排序(算法交换链表节点,时间复杂度O(nlogn),不考虑递归栈空间的话空间...归并排序应该算是链表排序最佳的选择了,保证了最好和最坏时间复杂度都是nlogn,而且它在数组排序中广受诟病的空间复杂度在链表排序

    归并排序(算法交换链表节点,时间复杂度O(nlogn),不考虑递归栈空间的话空间复杂度是O(1))                        本文地址

    首先用快慢指针的方法找到链表中间节点,然后递归的对两个子链表排序,把两个排好序的子链表合并成一条有序的链表。归并排序应该算是链表排序最佳的选择了,保证了最好和最坏时间复杂度都是nlogn,而且它在数组排序中广受诟病的空间复杂度在链表排序中也从O(n)降到了O(1)

    class Solution {
    public:
        ListNode *mergeSortList(ListNode *head) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            //链表归并排序
            if(head == NULL || head->next == NULL)return head;
            else
            {
                //快慢指针找到中间节点
                ListNode *fast = head,*slow = head;
                while(fast->next != NULL && fast->next->next != NULL)
                {
                    fast = fast->next->next;
                    slow = slow->next;
                }
                fast = slow;
                slow = slow->next;
                fast->next = NULL;
                fast = mergeSortList(head);//前半段排序
                slow = mergeSortList(slow);//后半段排序
                return merge(fast,slow);
            }
             
        }
        // merge two sorted list to one
        ListNode *merge(ListNode *head1, ListNode *head2)
        {
            if(head1 == NULL)return head2;
            if(head2 == NULL)return head1;
            ListNode *res , *p ;
            if(head1->val < head2->val)
                {res = head1; head1 = head1->next;}
            else{res = head2; head2 = head2->next;}
            p = res;
             
            while(head1 != NULL && head2 != NULL)
            {
                if(head1->val < head2->val)
                {
                    p->next = head1;
                    head1 = head1->next;
                }
                else
                {
                    p->next = head2;
                    head2 = head2->next;
                }
                p = p->next;
            }
            if(head1 != NULL)p->next = head1;
            else if(head2 != NULL)p->next = head2;
            return res;
        }
    };


    展开全文
  • 双向链表选择排序算法

    千次阅读 2014-12-16 18:27:31
    前日遇到一个问题:双向链表按关键字域进行排序。  在网上找了一下,都只一种算法,而且...于是自己想了一下,写了个带头结点的双向链表选择排序算法,指针的交换浓缩到4种情况,而且自认为选择排序函数中的结
  • 结点的单链表按数据域值从小到大进行选择排序的算法。 每一个链结点的数据域中存放一个数据,但头结点数据域中不存放任何信息。要求: (1)算法中不得增加和使用新的链结点空间 (2)不得改变链结点的数据域中原有的...
  • * Purpose: 对链表按学号进行排序 * Inputs:  1.pHead, 链表头指针 * Outputs:  NULL * Retrun Value: 返回int类型值 ****************************************************************/ int SortList...
  • C语言 链表数据的排序

    千次阅读 2021-02-25 22:04:49
    下边介绍使用链表时可用的排序方法,冒泡排序和选择排序。 此链表排序仅对链表中的数据进行排序,如果想进行对整个结构体的排序,也就是利用数据顺序来调整节点中的信息,需要对节点进行交换,但与此方法不同,望...
  • 在前面的博客中,已经写了关于数组和链表选择排序、冒泡排序和插入排序。在这里,再次补充快速排序。快排的应用场景很多,其中面试中广泛使用的就是在无序数集中查找第K个大(或小)的数值。下面,我们来处理一下该...
  • 在O(nlogn) 时间复杂度和常数级空间复杂度下,对链表进行排序。 2、示例 输入: 4->2->1->3 输出: 1->2->3->4 3、题解 基本思想:归并排序,不断分割链表直至每个节点都断开,然后不断两两合并...
  • 基数排序(radix sort)又称桶排序(bucket sort)...并且按照数字位的值数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的消耗复制时占用的空间,桶的数据结构选择链表,为了构造队列,选择使用双向列表。
  • 单向链表使用插入排序算法。 思想如下: 由于单向链表只能朝着一个方向遍历,因此设置当前节点current的前序节点pre。 比较过程中也需要设置两个节点,compare和它的前序节点precompare。 设置一个头节点head的...
  • 思路:因时间复杂度要求为O(N*logN),简单排序(时间复杂度为O(N*N))均不可用,故可以考虑归并排序的思想,归并排序对数组操作空间复杂度为O(n),但对链表为O(1),因为每次只在merge函数中创建了一个辅助的链表头...
  • #include #include #include #include char ppzz[100] = ""; ...char lwjj[100] = "";... fprintf(fp, "|%-6.6s|%-10.10s|%-10.10s|%-10.10s|%-12.12s|%-6.6s|\n", p->id, p->name, p->author, p->isbn, p->data, p->...
  • 链表排序相关

    2021-02-09 12:06:30
    文章目录链表结构题目要求一般做法说明选择排序插入排序快速排序归并排序 链表结构 给定的链表要么是单链表、要么是双链表,不过一般是单链表 题目要求 是否可以交换结点的值? 还是只能交换结点,值无法改变? 最...
  • 在O(nlogn)O(nlogn)O(nlogn)的时间复杂度和O(1)O(1)O(1)的空间复杂度内对链表进行排序。 例如: 输入: 3->2->1->5->4 输出:1->2->3->4->5 2、解题思路 思路1:最简单的方法是利用选择...
  • 单链表实现选择排序

    2021-02-01 22:50:28
    第二部分的链表存的是p1-p2之间所有的结点,第三部分的链表存的是p2后面的所有结点,然后每次for循环时分8种情况(每个部分存在与否)对三个链表和p1 p2进行组合,最后即可对链表进行选择排序。 代码实现 #include&...
  • 在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序。 2、代码详解 2.1 归并排序(常用) 2.2 快速排序 快速排序的最坏时间复杂度是 o(n*n),均摊复杂度才是 o(nlogn)。除非用 bfprt 等算法先进行...
  • 数据结构--链表排序详解

    万次阅读 多人点赞 2016-11-18 22:18:26
    但是,我突然发现在链表这里我缺少一个很重要的内容,那就是我们的链表进行排序,其实,在连接两个链表的时候,就要求我们的那两个链表是有序的。2、链表排序—最简单、直接的方式(直接采用冒泡或者选择排序,...
  • 用指针p遍历链表head找出当前链表中的值最大的结点,用pmax指向该结点。然后利用qmax将该最大值结点从链表head中删除,利用头插法插入链表head1中。 重复操作即可 代码如下: 结构体定义: typedef struct ...
  • 身高都是先处理为降序再进行重新排列的,而后排的同学都比前排的高,所以可以直接所有的人先进行一次身高升序排序(同时名字降序排序),然后从后往前处理数据,对于每一组,选择这一组元素下标最大的那个元素,...
  • 1。单向链表的选择排序。时间复杂度O(n^2)空间复杂度O(1) (1)方法一 可以交换链表的值,不改变链表的指向。 (2)方法二 找到原链表值最小的节点,...利用归并对链表进行排序。题目链接:148. Sort List
  • 问题:我们需要将一个无序的单链表在 O(n log n) 时间复杂度和常数级空间复杂度下,对链表进行排序 时间复杂度为稳定O(n log n)的排序只有堆排序与归并排序,但是堆排序需要建堆,那么链表有n个节点我们就需要...
  • 双向链表排序

    千次阅读 2008-07-28 16:44:00
    以前写过双向链表交换任意结点的程序,后来写了个双向链表排序的程序,没用边输入边排序的思想,是输入完毕后我按照选择排序的思想对链表的结点进行交换.是地址交换.#include typedef struct Link/*双向链表结构体*/{...
  • leetcode 148 排序链表

    2021-03-10 19:33:51
    就是一个链表进行排序。。 我采取得快排的思路,提交超过5%。。。看list标准库是用归并排序实现的,过几天改下的,现在先把链表快排的思路放上: 选择target(即基础点,左边的元素都小于target,右边的都大于...
  • 链表归并排序的递归与非递归实现

    千次阅读 2015-09-20 21:27:39
    算法思想是首先用快慢指针的方法找到链表中间节点,然后递归地两个子链表进行排序,把两个排好序的子链表合并成一条有序的链表。归并排序算是链表排序中的最好选择,保证了最好和最坏时间复杂度都是NlogN,而且它...
  • 对链表进行排序,方法很多,由于要求时间复杂度是O(nlogn)空间复杂度是常量级别,所以我们需要在众多排序中做选择,满足这个时间复杂度的排序算法有快速排序,堆排序,希尔排序和归并排序。由于快排在最坏情况下的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 427
精华内容 170
关键字:

对链表进行选择排序