行业知识
leetcode:反转链表II 和k个一组反转链表的C++实现
反转链表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* 是指向经过部分反转后的链表的头节点的指针。
函数内部逻辑
- 创建一个新的头节点 newhead,其值为0,并将其 next 指针指向原链表的头节点 head。这是为了方便处理边界情况,特别是当 left 为1时。
- 初始化一个计数器 i 为1,用于记录当前的位置。
- 初始化一个指针 pre,它将用于跟踪第 left-1 个节点,即反转部分的前一个节点。
- 使用 while 循环将 pre 指针移动到第 left-1 个节点的位置。
- 初始化另一个指针 cur,它将用于跟踪当前要进行反转操作的节点,初始时指向第 left 个节点。
- 使用另一个 while 循环,在 i 小于 right 时进行反转操作,并确保 cur 不为空:
- 将 pnext 指向 cur 的下一个节点。
- 将 cur 的 next 指针指向 pnext 的下一个节点,这样就从链表中断开了 pnext。
- 将 pnext 的 next 指针指向 pre 的下一个节点,这样 pnext 就移动到了反转部分的开始位置。
- 将 pre 的 next 指向 pnext,这样就将 pnext 插入到了反转部分的开始位置。
- 增加计数器 i。
- 循环结束后,从位置 left 到位置 right 的链表部分已经被反转。
- 返回 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* 是指向经过分组反转后的链表的头节点的指针。
函数内部逻辑
- 首先检查是否需要进行操作,如果链表为空 (nullptr) 或 k 等于1(即不需要分组反转),则直接返回原链表的头节点 head。
- 创建一个哑节点 dummy,其值为0,并将其 next 指针指向原链表的头节点 head。这是为了方便操作,特别是当链表的头部需要被反转时。
- 初始化三个指针 pre、cur 和 nex,它们都指向哑节点 dummy。pre 将用于跟踪每组反转前的第一个节点的前一个节点,cur 将用于遍历链表,而 nex 将用于反转操作中的节点交换。
- 初始化计数器 count 为0,用于记录链表的长度。
- 使用 while 循环计算链表的长度,并将长度存储在 count 中。
- 使用另一个 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,表示已经完成了一组节点的反转。
- 循环结束后,所有的 k 个节点的组都已经被反转,不足 k 个节点的组保持原样。
- 返回 dummy->next,即新链表的头节点,因为 dummy 是一个哑节点。
总结
此代码通过迭代的方式,每次反转链表中的 k 个节点。它首先使用一个哑节点简化操作,然后通过两个循环,一是计算链表长度,二是进行分组反转。最终返回新链表的头节点。