25. K 个一组翻转链表 - 力扣（LeetCode）
标题：给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。假如节点总数不是 k 的整数倍，那么请将末了剩余的节点保持原有次序。
你不能只是单纯的改变节点内部的值，而是需要现实进行节点交换。
示例 1：
https://i-blog.csdnimg.cn/img_convert/2cf7a2600281e6e3f56b9e10c24beefa.jpeg
输入：head = , k = 2
输出： 示例 2：
https://i-blog.csdnimg.cn/img_convert/94834b81cffd8aba793089ca9dd1c2e1.jpeg
输入：head = , k = 3
输出： 提示：
[*] 链表中的节点数量为 n
[*] 1 <= k <= n <= 5000
[*] 0 <= Node.val <= 1000
思绪如下：
本题的思绪是基于链表的分组反转操纵。具体来说，就是将链表的节点每 k 个为一组进行反转。首先统计链表的节点个数，如许可以知道是否尚有充足的节点来进行分组反转。创建一个虚拟头节点 dummy ，这个虚拟头节点的 next 指向原链表的头节点，然后初始化三个指针：p0 指向当前处理组的前一个节点（初始为虚拟头节点），pre 用于保存当前节点的前一个节点（初始为 None），cur 用于遍历链表（初始为头节点 head）。
在分组反转的过程中，每次处理 k 个节点的一组，直到剩余节点数不敷 k 个。在每次处理时，通过一个循环逐个反转节点，保存当前节点的下一个节点到 nxt，将当前节点的 next 指向 pre 实现反转，然后更新 pre 和 cur 指针。
反转完成后，需要将反转后的子链表毗连到主链表中。这里通过 p0.next 指向反转后的组头节点 pre，而反转前的组头节点（nxt）的 next 指向当前 cur（下一组的第一个节点），末了更新 p0 到下一组的前一个节点。
这里用表示图俩表示题解实例中完成第一个 k 的反转后的链表，以便参考：
https://i-blog.csdnimg.cn/direct/314c433504304aafb290fbf0d609424b.png
题解如下：
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseKGroup(self, head: Optional, k: int) -> Optional:
# 统计链表的节点个数
n = 0
cur = head
while cur:
n += 1
cur = cur.next
# 创建一个虚拟头节点
p0 = dummy = ListNode(next=head)
# pre用于记录当前反转部分的前一个节点，cur用于遍历链表
pre = None
cur = head
# 每次处理k个节点的一组
while n >= k:
# 减少剩余需要处理的节点数
n -= k
# 反转当前组的k个节点
for i in range(k):
# 保存当前节点的下一个节点
nxt = cur.next
# 将当前节点的next指向前一个节点pre，实现反转
cur.next = pre
# 更新pre和cur的位置
pre = cur
cur = nxt
# 连接反转后的子链表到主链表中
# nxt是p0的下一个节点，即反转前的组头节点
nxt = p0.next
# 将反转后的组尾节点（nxt）的next指向当前cur（下一组的第一个节点）
nxt.next = cur
# 将p0的next指向反转后的组头节点pre
p0.next = pre
# 更新p0到下一组的前一个节点（即当前组的尾节点nxt）
p0 = nxt
# 返回虚拟头节点的next，即新的链表头
return dummy.next
题解示例：
假设链表为 1 -> 2 -> 3 -> 4 -> 5 -> None，k=2。
统计节点个数：n = 5。
创建虚拟头节点：dummy.next = 1 -> 2 -> 3 -> 4 -> 5 -> None。
初始化指针：p0 指向 dummy，pre = None，cur = 1。
第一次处理 k=2 个节点：
反转 1 -> 2，得到 2 -> 1。
连接反转后的子链表：
nxt = 1（p0.next）。
1.next = 3（当前 cur）。
p0.next = 2（反转后的组头节点）。
更新 p0 到 1。
第二次处理 k=2 个节点：
反转 3 -> 4，得到 4 -> 3。
连接反转后的子链表：
nxt = 3（p0.next）。
3.next = 5（当前 cur）。
p0.next = 4（反转后的组头节点）。
更新 p0 到 3。
剩余节点数不足 k，停止处理。
最终链表为 2 -> 1 -> 4 -> 3 -> 5 -> None。
逻辑梳理：
1. 统计链表节点个数
首先，遍历链表统计节点总数 n，这有助于判定是否尚有充足的节点进行分组反转。
2. 创建虚拟头节点
创建一个虚拟头节点 dummy，其 next 指向原链表的头节点。这可以简化界限条件的处理，好比当链表为空或者只有一个节点时的操纵。
3. 初始化指针
[*] p0：指向当前处理组的前一个节点，初始为虚拟头节点。
[*] pre：用于保存当前节点的前一个节点，初始为 None。
[*] cur：用于遍历链表，初始为头节点 head。
4. 分组反转逻辑
每次处理 k 个节点的一组，直到剩余节点数不敷 k 个：
[*] 减少剩余节点数：n -= k，表示已经处理了一组 k 个节点。
[*] 反转当前组的 k 个节点：
[*] 使用一个循环，遍历 k 次，逐个反转节点。
[*] 在每次循环中：
[*] 保存当前节点的下一个节点到 nxt。
[*] 将当前节点的 next 指向 pre，实现反转。
[*] 更新 pre 和 cur 指针。
5. 毗连反转后的子链表
[*] nxt 是 p0 的下一个节点，即反转前的组头节点。
[*] 将反转后的组尾节点（nxt）的 next 指向当前 cur（下一组的第一个节点）。
[*] 将 p0 的 next 指向反转后的组头节点 pre。
[*] 更新 p0 到下一组的前一个节点（即当前组的尾节点 nxt）。
6. 返回效果
返回虚拟头节点的 next，即新的链表头。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]