大连网站建设免费,合肥seo网络优化公司,wordpress 30天,乌市建设工程质量监督站网站我听别人说这世界上有一种鸟是没有脚的#xff0c;它只能够一直的飞呀飞呀#xff0c;飞累了就在风里面睡觉#xff0c;这种鸟一辈子只能下地一次#xff0c;那一次就是它死亡的时候。——《阿甘正传》这一文章讲解链表的奇偶排序问题#xff0c;这是一道不难但是挺好的链…我听别人说这世界上有一种鸟是没有脚的它只能够一直的飞呀飞呀飞累了就在风里面睡觉这种鸟一辈子只能下地一次那一次就是它死亡的时候。——《阿甘正传》这一文章讲解链表的奇偶排序问题这是一道不难但是挺好的链表题目有一些题目就是基于奇偶排序拓展出来的。目录一.原题二.双指针在链表中的应用三.具体思路与做法四.具体代码一.原题接下来给出原题以供大家思考二.双指针在链表中的应用双指针的作用由于单向链表(如上图)的每一个指针只能从头往后扫描并不能从后往前的这一个局限性。所以我们在解决单向链表的题目上引入双指针。双指针指的是在遍历对象的过程中不是普通的使用单个指针进行访问而是使用两个指针特殊情况甚至可以多个两个指针或是同方向访问两个链表或是同方向访问一个链表快慢指针、或是相反方向扫描对撞指针从而建立一种手段让这种手段为我们的目的服务。三.具体思路与做法1.具体思路psodd 奇数 even偶数设oddhead(odd指向head也即结点1) evenhead-nexteven指向结点2 xianjiehead-next(用来连接两个奇偶链表)如下图所示第一个结点是奇数位第二个结点是偶数第二个结点后又是奇数位。因此可以断掉结点1和结点2之间的连接让结点1指向结点2的后面即结点3。代码也即(odd-nexteven)如红色箭头。如果此时我们将第一个结点指向第三个结点,代码也即(oddodd-next)就可以得到那么第三个结点后为偶数结点因此我们又可以断掉结点2到结点3之间的连接指向结点3后一个结点即结点4代码也即(even-nextodd-next)如蓝色箭头。那么我们再将第二个结点指向第四结点代码也即(eveneven-next)接下来就是循环这一整个步骤直到快指针(odd为NULL)。2.具体做法step 1判断空链表的情况如果链表为空不用重排。step 2使用双指针odd和even分别遍历奇数节点和偶数节点并给偶数节点链表一个头。step 3上述过程每次遍历两个节点且even在后面因此每轮循环用even检查后两个元素是否为NULL如果不为再进入循环进行上述连接过程。step 4将偶数节点头接在奇数最后一个节点后再返回头部。四.具体代码 ListNode* oddEvenList(ListNode* head) {//边界治理if (head nullptr || head-next nullptr)return head;ListNode* odd head;ListNode* even head-next;ListNode* xianjie head-next;while (even-next ! nullptr even ! nullptr) {odd-next even-next;odd odd-next;even-next odd-next;even even-next;}odd-next xianjie;//奇数的最后一个结点指向第二个结点(偶数结点)形成奇偶序列return head;}};大家加油。。。。。最近在做算法题目考研关注我点个赞有问题可以一起讨论。以后的几篇文章都讲解链表题目。
