C/C++ BM3 链表中的节点每k个一组翻转

2023-12-30 21:42:19

前言

这道题的关键是理解链表指针的位置;
在BM2的区间翻转基础上,多了个指针偏移,博客里面我贴图阐述一下。


题目

在这里插入图片描述

思路阐述

这道题的翻转过程参考BM2的题解,这里主要阐述一下指针移动和整体思路。

题目的要求是链表中的每k个一组翻转,也就是说每k个就是一个区间,区间的长度为k。
那对于一个输入的完整的链表,要执行区间翻转这个整体操作几次呢?我这里采用链表长度count除以区间长度,再取整的方式来得知。比如给定的链表长度为5,k值为2。那么每两个节点就是一个区间,5/2的值是2.5,取个整就是2,也就是说要翻转区间两次。
如果链表长度小于k值,那得到的次数肯定是0,我们也就不需要翻转了。

区间翻转:里面翻转的次数是几次呢?比如有3个节点(k值为3,区间长度),我们参考BM2的解法,其实只需要调整两个节点的位置就可以了,123变成321,只需要把2,3依次拿到1,和21前面即可。如果k值是2,区间长度为2,区间的节点为1,2。我们只需要把1,2的值翻转k-1=1次即可,2放到1的前面。写这个的原因是循环里面j为什么1开始而不是从0

移动新区间:
翻转一个区间之后,效果大致如下图。
我们可以看到intervalHead指针的位置在当前翻转区间的后节点,而非新的翻转区间,pre的位置还是在总链表的表头位置,而非intervalHead的前一个位置。

为什么要这样调整?因为是把总的链表分割成一个一个的子区间进行翻转,所以每次翻转的时候都要和初始情况的指针位置保持一致。因为翻转主要用到的是前序节点pre和区间链表的表头intervalHead,所以这两个指针的位置需要调整。
在这里插入图片描述

代码

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @param k int整型
     * @return ListNode类

     思路一:区间翻转的进阶。
     首先确定一下这个链表的长度,每次翻转一个区间,区间翻转次数就是长度count除以k的值
     区间翻转

     */
    ListNode* reverseKGroup(ListNode* head, int k) {
        //计算节点个数
        int count = CountNodeNumber(head);
        //添加头结点-1
        ListNode* selfHead = new  ListNode(-1);
        selfHead->next = head;
        //添加区间链表的表头
        ListNode* intervalHead = head;
        //添加前序节点
        ListNode* pre = selfHead;

        int temptime = count / k;
        for(int i=0;i<temptime;i++)
        {
            //区间翻转
            for (int j = 1; j < k; j++) {
            //断开节点
            ListNode* temp = intervalHead->next;
            intervalHead->next = temp->next;
            //插入节点
            temp->next = pre->next;
            pre->next = temp;
            }
            //移动到新区间
            for(int x=0;x<k;x++)
            {
                pre=pre->next;
            }
            intervalHead=intervalHead->next;
        }
        return selfHead->next;
    }
    int CountNodeNumber(ListNode* head) {
        int count = 0;
        while (head) {
            count++;
            head = head->next;
        }
        return count;
    }
};

总结

BM3应该是链表翻转的最终题了。
从BM1的翻转链表,到BM2的区间翻转,再到BM3的分段区间翻转。确实让我对链表有了更深刻的理解。

链表中的断链和接链的操作要注意顺序,在插入节点的时候比较重要。插入节点的时候要先把节点指向新链表,再断链表相连。

链表确定数据长度需要使用while循环来依次遍历,并使用一个int类型的变量进行计数。因为链表存放的数据在内存中是不连续的,所以不支持下表访问,也不能用sizeof这种函数。

链表一般都要有个头结点,一般头结点不包含数据,我这几道题里面加了个值为-1的节点,其实在实际操作链表的时候很有用。因为head指针的位置很容易发生改变,但是如果前面加一个头结点,我们后面对指针的操作之后,再找头结点就非常方便。

文章来源:https://blog.csdn.net/Edwinwzy/article/details/135295953
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。