0


【链表】链表OJ-力扣2074. 反转偶数长度组的节点【超详细的算法解释】

说在前面

今天博主给大家带来的是力扣上的一道链表OJ,完成这道题后,博主感觉这题覆盖了很多链表的解题思想,另外,这道题对指针的控制也是比较高的。在这里博主将这道好题分享给大家!
另外,对于链表等数据结构还没有很熟悉的伙伴,可以通过传送门食用!

  • 2074. 反转偶数长度组的节点
  • 手撕数据结构专栏

导航小助手

博主给大家的话

在这里插入图片描述

那么这里博主先安利一下一些干货满满的专栏啦!

数据结构专栏:手撕数据结构 这里包含了博主很多的数据结构学习上的总结,每一篇都是超级用心编写的,有兴趣的伙伴们都支持一下吧!
算法专栏:算法 这里可以说是博主的刷题历程,里面总结了一些经典的力扣上的题目,和算法实现的总结,对考试和竞赛都是很有帮助的!
力扣刷题专栏:跟着博主刷Leetcode 想要冲击ACM、蓝桥杯或者大学生程序设计竞赛的伙伴,这里面都是博主的刷题记录,希望对你们有帮助!
C的深度解剖专栏:C语言的深度解剖 想要深度学习C语言里面所蕴含的各种智慧,各种功能的底层实现的初学者们,相信这个专栏对你们会有帮助的!

题目描述

在这里插入图片描述

解题思路

思路:
首先我们想到的大致思路是,先定义两个指针

fast

slow

fast

往前走,走几步之后,我们反转

fast

slow

之间的链表,再拼接起来。

又因为现在题目所给链表是不带头的,**

slow

指向的节点,是我们要反转的链表的头节点(如果需要要反转的话),而

fast

所指向的节点是要反转的链表的尾节点的后一个节点。**
就拿例子1来举例子,我们的指针位置应该是这样的:
在这里插入图片描述

  • 那我们该如何去找这个反转区间呢,这个很简单,第一次fast走一步,第二次走两步,第三次走三步…,当fast走的步数是偶数次时,反转。

如果要反转一个区间的链表,光有这两个指针是不够的。
假设我们刚才要反转

[2,6]

那个区间的链表,我们必须先让

6

next

置空,然后反转

2

开头的链表,再链接到

5

上,然后再把尾链接到

3

上,**所以我们还需要两个指针,

slow_prev

fast_prev

,分别指向

fast

的前一个节点和

slow

的前一个节点。**


完整的实现代码

// 2074. 反转偶数长度组的节点classSolution{private:structListNode*reverseList(structListNode* head){structListNode* newhead =NULL;if(head ==NULL){return head;}structListNode* cur = head;structListNode* next = head->next;while(cur !=NULL){
            cur->next = newhead;
            newhead = cur;
            cur = next;if(cur !=NULL){
                next = cur->next;}}return newhead;}public:
    ListNode*reverseEvenLengthGroups(ListNode* head){if(head ==NULL|| head->next ==NULL)return head;
        ListNode* slow_prev = head;
        ListNode* fast_prev = head;
        ListNode* fast = head;
        ListNode* slow = head;for(int i =1;; i++){int i_tmp = i;while(i_tmp && fast){
                fast_prev = fast;
                fast = fast->next;
                i_tmp--;//这个一定要放在里面,否则就减多一次了!}if((i - i_tmp)%2==0){//有可能最后一个区间走不完,所以只需要看走了多少步//反转链表
                fast_prev->next =NULL;
                slow_prev->next =reverseList(slow);//找尾while(slow_prev->next){
                    slow_prev = slow_prev->next;}
                slow_prev->next = fast;
                slow = fast;
                fast_prev = slow_prev;}else{//不用反转
                slow_prev = fast_prev;
                slow = fast;}if(fast ==NULL)break;}return head;}};

调试代码(编译器调试用)

如果我们在自己写这道题时遇到困难,需要复制到本地IDE上调试,博主把链表弄好了提供给大家,大家直接调试接口就好了!

ListNode*_CreatListNode(int x);voidListPushBack(ListNode** pphead,int x);intmain(){//[5,2,6,3,9,1,7,3,8,4]
    Solution su;
    ListNode* head =NULL;ListPushBack(&head,5);ListPushBack(&head,2);ListPushBack(&head,6);ListPushBack(&head,3);ListPushBack(&head,9);ListPushBack(&head,1);ListPushBack(&head,7);ListPushBack(&head,3);ListPushBack(&head,8);ListPushBack(&head,4);//从这里开始调试
    ListNode* ret = su.reverseEvenLengthGroups(head);return0;}

ListNode*_CreatListNode(int x){
    ListNode* newNode =(ListNode*)malloc(sizeof(ListNode));
    newNode->val = x;
    newNode->next =NULL;return newNode;}voidListPushBack(ListNode** pphead,int x){
    ListNode* newNode =_CreatListNode(x);//空链表的情况if(*pphead ==NULL){*pphead = newNode;}else{//找尾
        ListNode* tail =*pphead;while(tail->next !=NULL){
            tail = tail->next;}
        tail->next = newNode;}}

尾声

看到这里,相信你已经学会这道题了,如果你感觉这篇博客对你有帮助的话,不要忘了一键三连哦!

标签: 算法 链表 leetcode

本文转载自: https://blog.csdn.net/Yu_Cblog/article/details/125018821
版权归原作者 #西城s 所有, 如有侵权,请联系我们删除。

“【链表】链表OJ-力扣2074. 反转偶数长度组的节点【超详细的算法解释】”的评论:

还没有评论