问题描述
给你一个链表，每个链表上的节点数目为 n，请你将链表的每个 k 个节点反转，返回反转后的链表。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
进一步说明：
- 链表中节点的数目在范围
[1, 5000]内 0 <= Node.val <= 10001 <= k <= 2000
示例
输入： head = [1,2,3,4,5], k = 2 输出： [2,1,4,3,5]
解释： 节点总数为 5，不是 2 的整数倍，因此最后剩下的一个节点保持原有顺序。
分治策略
分治策略，其中“分”是指将链表分成多个长度为 k 的部分，而“治”则是对每部分应用翻转操作。这样，可以高效地在单链表上实现复杂的数据重组，而不需要额外的空间开销（即空间复杂度为 O(1)），因为所有操作均在原链表上就地完成。
要求对链表中的节点进行局部翻转。主要思路是：
- 遍历链表，计算链表长度
n。 - 对链表的每个
k个节点进行翻转操作。如果链表剩余节点少于k个，则不进行翻转。 - 使用一个虚拟头节点简化边界处理，保持对翻转链表头部的引用。
- 使用三指针法（prev, curr, next）进行局部翻转。
- 注意处理每个翻转段的首尾连接问题。
代码实现
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverseKGroup(head, k): if not head or k == 1: return head # 创建一个虚拟头节点 dummy = ListNode(0) dummy.next = head prev_group = dummy while True: kth = prev_group # 找到第 k 个节点 for i in range(k): kth = kth.next if not kth: return dummy.next group_next = kth.next # 翻转 [prev_group.next, kth] prev, curr = kth.next, prev_group.next while curr != group_next: temp = curr.next curr.next = prev prev = curr curr = temp temp = prev_group.next prev_group.next = kth prev_group = temp return dummy.next # 链表构造及调用 nodes = [ListNode(i) for i in range(1, 6)] for i in range(len(nodes) - 1): nodes[i].next = nodes[i + 1] head = nodes[0] result = reverseKGroup(head, 2) while result: print(result.val, end=" ") result = result.next
输出
2 1 4 3 5
图解说明
1.初始链表状态
链表：1 -> 2 -> 3 -> 4 -> 5，其中 k = 2。
2.添加虚拟头结点
为了方便操作，我们首先添加一个虚拟头结点（dummy node）：
Dummy -> 1 -> 2 -> 3 -> 4 -> 5
3.第一次翻转过程（翻转1和2）
定位第k个节点
我们需要定位到第 k 个节点（2），这样我们就知道从哪里开始到哪里结束翻转。
Dummy -> 1 -> 2 -> 3 -> 4 -> 5 | | start kth
执行翻转
接下来，我们需要翻转从 start（1）到 kth（2）的部分。翻转操作如下：
Before: Dummy -> 1 -> 2 -> 3 -> 4 -> 5 | | start kth After: Dummy -> 2 -> 1 -> 3 -> 4 -> 5
4.第二次翻转过程（翻转3和4）
定位第k个节点
和之前一样，我们移动到下一个未翻转的部分的第 k 个节点（4）。
Dummy -> 2 -> 1 -> 3 -> 4 -> 5 | | start kth
执行翻转
翻转从 start（3）到 kth（4）的部分。翻转操作如下：
Before: Dummy -> 2 -> 1 -> 3 -> 4 -> 5 | | start kth After: Dummy -> 2 -> 1 -> 4 -> 3 -> 5
5.结果输出
最终的链表结构为：
Dummy -> 2 -> 1 -> 4 -> 3 -> 5
我们从虚拟头结点的下一个节点开始输出，即得到翻转后的链表：
2 -> 1 -> 4 -> 3 -> 5
算法分析
时间复杂度：O(n)，其中 n 是链表的长度，我们需要遍历整个链表进行分组和翻转。 空间复杂度：O(1)，只使用有限的几个指针，不需要额外空间。
核心思想
- 虚拟头节点：引入虚拟头节点简化了链表头部的翻转逻辑，避免了复杂的边界条件判断。
- 分组定位：通过双指针技术精确定位每
k个节点的分组，确保了翻转的准确性和效率。 - 局部翻转：在每个分组内部实现节点的就地翻转，使用了三指针策略来逐个调整节点指向。
解题思路：迭代 + 栈 方法
在这种方法中，我们将利用栈的特性来帮助我们实现链表的局部翻转。栈可以让我们简单地实现先进后出的顺序，正好符合翻转的需求。以下是使用迭代加栈方法进行 K 个一组翻转链表的详细步骤和完整代码实现。
算法步骤
1. 初始化：创建一个哑结点（dummy node）作为新链表的头部。这可以简化边界条件处理，使得头部处理逻辑与中间部分相同。
2. 遍历链表：使用指针 current 遍历原链表。
3. 填充栈：每遍历一个节点，就将其压入栈中。一旦栈的大小达到 k，就进行下一步。
4. 翻转操作：栈中元素数量达到 k 后，依次弹出栈中元素，并重建链表的这部分，从而实现局部翻转。
5. 连接链表：翻转后的链表部分需要与主链表正确连接。使用一个 prev 指针帮助记录每个部分的最后一个节点，以便连接。
6. 处理剩余部分：如果链表的长度不是 k 的整数倍，最后剩余的节点保持原有顺序连接。
python示例
class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def reverseKGroup(head: ListNode, k: int) -> ListNode: if head is None or k == 1: return head # 创建一个哑结点作为新链表的头部 dummy = ListNode(0) dummy.next = head current = head prev = dummy stack = [] # 遍历链表 while current: # 填充栈，直到栈的大小达到 k stack.append(current) next_temp = current.next if len(stack) == k: # 当栈的大小为 k 时，进行翻转 while stack: if prev: prev.next = stack.pop() prev = prev.next # 翻转完成后，连接剩余的部分 prev.next = next_temp # 移动当前指针到下一个节点 current = next_temp return dummy.next # 链表节点创建和测试代码 # 创建链表 1->2->3->4->5 node1 = ListNode(1) node2 = ListNode(2) node3 = ListNode(3) node4 = ListNode(4) node5 = ListNode(5) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 # 设置 k = 3 k = 3 new_head = reverseKGroup(node1, k) # 打印新链表的结构 current = new_head while current: print(current.val, end=" -> ") current = current.next
输出结果示例
对于链表 1->2->3->4->5 和 k = 3 的设置，输出应该是：
3 -> 2 -> 1 -> 4 -> 5 ->
这里的代码演示了如何使用栈结合迭代方法进行链表的局部翻转，并确保了整体链表结构的正确性。这种方法的空间复杂度为 O(k)，时间复杂度为 O(n)，是一种有效且易于理解的解决方案。
欢迎关注微信公众号 数据分析螺丝钉
