小工具知识网

当前位置: 首页 > 行业知识 > leetcode:反转链表II 和k个一组反转链表的C++实现

行业知识

leetcode:反转链表II 和k个一组反转链表的C++实现

2026-11-16 13:10:57 来源:互联网转载

反转链表II

问题描述

���你单链表的头指针 head 和两个整数 left 和 right ,其中 left next = head; int i = 1; ListNode* pre = newhead; while(i next; i++; } ListNode* cur = pre->next; ListNode* pnext; while(i next; cur->next = pnext->next; pnext->next = pre->next; pre->next = pnext; i++; } return newhead->next;}

 

这段代码定义了一个函数 reverseBetween,该函数的目的是反转一个单链表中从位置 left 到位置 right 的部分链表。链表的节点定义采用 ListNode 结构。

()
函数参数和返回值
  • 参数 ListNode* head 是指向链表第一个节点的指针。
  • 参数 int left 是需要开始反转的起始位置。
  • 参数 int right 是需要结束反转的终止位置。
  • 返回值 ListNode* 是指向经过部分反转后的链表的头节点的指针。
    函数内部逻辑
    1. 创建一个新的头节点 newhead,其值为0,并将其 next 指针指向原链表的头节点 head。这是为了方便处理边界情况,特别是当 left 为1时。
    2. 初始化一个计数器 i 为1,用于记录当前的位置。
    3. 初始化一个指针 pre,它将用于跟踪第 left-1 个节点,即反转部分的前一个节点。
    4. 使用 while 循环将 pre 指针移动到第 left-1 个节点的位置。
    5. 初始化另一个指针 cur,它将用于跟踪当前要进行反转操作的节点,初始时指向第 left 个节点。
    6. 使用另一个 while 循环,在 i 小于 right 时进行反转操作,并确保 cur 不为空:
      • 将 pnext 指向 cur 的下一个节点。
      • 将 cur 的 next 指针指向 pnext 的下一个节点,这样就从链表中断开了 pnext。
      • 将 pnext 的 next 指针指向 pre 的下一个节点,这样 pnext 就移动到了反转部分的开始位置。
      • 将 pre 的 next 指向 pnext,这样就将 pnext 插入到了反转部分的开始位置。
      • 增加计数器 i。
    7. 循环结束后,从位置 left 到位置 right 的链表部分已经被反转。
    8. 返回 newhead->next,即新链表的头节点,因为 newhead 是一个哑节点。
    总结

    此代码通过迭代的方式,反转了单链表的一部分。它首先使用一个哑节点简化操作,然后通过两个循环移动节点,逐步实现链表的局部反转。最终返回新链表的头节点。

    k个一组反转链表

    问题描述

    以 k 个节点为一组进行链表翻转,即每 k 个节点之内进行翻转,如果最后一组不足 k 个节点,则不进行翻转。

    解决方案

    以下是 C++ 代码实现:

    ListNode* reverseKGroup(ListNode* head, int k) {    if (head == nullptr || k == 1) {        return head;    }    ListNode* dummy = new ListNode(0);    dummy->next = head;    ListNode *pre = dummy, *cur = dummy, *nex = dummy;    int count = 0;        // 计算链表长度    while (cur->next != nullptr) {        cur = cur->next;        count++;    }        // 根据链表长度计算需要翻转的次数    while (count >= k) {        cur = pre->next; // 重置当前节点为组的第一个节点        nex = cur->next; // 重置下一个节点                // 进行 k-1 次翻转        for (int i = 1; i next = nex->next;            nex->next = pre->next;            pre->next = nex;            nex = cur->next;        }                pre = cur; // 将 pre 移动到下一组的开始位置        count -= k; // 减少 k 个计数    }        return dummy->next;}

    这段代码定义了一个函数 reverseKGroup,用于按照给定的大小 k 反转一个单链表中的节点组。反转是以每 k 个节点为一组进行的,最后不足 k 个节点的组不会被反转。

    函数参数和返回值
    • 参数 ListNode* head 是指向链表第一个节点的指针。
    • 参数 int k 是每组中的节点数量。
    • 返回值 ListNode* 是指向经过分组反转后的链表的头节点的指针。
      函数内部逻辑
      1. 首先检查是否需要进行操作,如果链表为空 (nullptr) 或 k 等于1(即不需要分组反转),则直接返回原链表的头节点 head。
      2. 创建一个哑节点 dummy,其值为0,并将其 next 指针指向原链表的头节点 head。这是为了方便操作,特别是当链表的头部需要被反转时。
      3. 初始化三个指针 pre、cur 和 nex,它们都指向哑节点 dummy。pre 将用于跟踪每组反转前的第一个节点的前一个节点,cur 将用于遍历链表,而 nex 将用于反转操作中的节点交换。
      4. 初始化计数器 count 为0,用于记录链表的长度。
      5. 使用 while 循环计算链表的长度,并将长度存储在 count 中。
      6. 使用另一个 while 循环,只要 count 大于或等于 k,就执行以下操作:
        • 重置 cur 为当前组的第一个节点,即 pre 的下一个节点。
        • 重置 nex 为 cur 的下一个节点。
        • 进行 k-1 次反转操作,因为每组的第一个节点不需要移动,只需移动剩余的 k-1 个节点:
          • 将 cur 的 next 指向 nex 的下一个节点,这样就从链表中断开了 nex。
          • 将 nex 的 next 指向 pre 的下一个节点,这样 nex 就移动到了当前组的开始位置。
          • 将 pre 的 next 指向 nex,这样就将 nex 插入到了当前组的开始位置。
          • 更新 nex 为 cur 的下一个节点,为下一次迭代做准备。
        • 在完成一组节点的反转后,将 pre 移动到这组的最后一个节点,即当前的 cur,准备进行下一组的反转。
        • 从 count 中减去 k,表示已经完成了一组节点的反转。
      7. 循环结束后,所有的 k 个节点的组都已经被反转,不足 k 个节点的组保持原样。
      8. 返回 dummy->next,即新链表的头节点,因为 dummy 是一个哑节点。
      总结

      此代码通过迭代的方式,每次反转链表中的 k 个节点。它首先使用一个哑节点简化操作,然后通过两个循环,一是计算链表长度,二是进行分组反转。最终返回新链表的头节点。

       

上一篇:Gamestars下载攻略,一键获取游戏之星,开启你的游戏世界!

下一篇:小区中控室主机怎么接线