【链表】链表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;}}

尾声

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