Algorithms 101: 反转 K 个一组的链表

反转 K 个一组的链表详解及示例

在链表操作中，反转每 K 个节点是一道经典问题，它测试了我们对递归和链表指针操作的理解。本文将详细讲解如何实现反转 K 个一组的链表，并通过示例帮助理解。

问题定义

给定一个链表，要求每 K 个节点为一组进行反转，并返回反转后的链表。如果剩余节点不足 K 个，则保持原有顺序。

例子：

输入：

head = 1 -> 2 -> 3 -> 4 -> 5, k = 3

输出：

3 -> 2 -> 1 -> 4 -> 5

注意：

必须按照 K 个一组反转。
最后不足 K 个的节点保持原顺序。

思路

我们可以通过递归实现反转 K 个一组的链表：

统计节点数：遍历链表，检查是否有至少 K 个节点。如果不足 K 个，直接返回当前链表。
递归反转：当有 K 个节点时，递归处理剩余链表，并返回已反转部分的新头节点。
反转当前组：反转当前组的 K 个节点，将其连接到递归返回的部分。

实现代码

以下是完整的代码实现，包含详细注释：

# 单链表节点定义
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        cur = head
        group = 0

        # 1. 检查当前组是否有至少 K 个节点
        while cur and group < k:
            cur = cur.next
            group += 1

        # 2. 如果有 K 个节点，则递归反转剩余链表
        if group == k:
            cur = self.reverseKGroup(cur, k)  # 递归反转后续部分
            # 3. 反转当前组的 K 个节点
            while group > 0:
                tmp = head.next  # 暂存下一个节点
                head.next = cur  # 当前节点指向已反转部分
                cur = head  # 更新反转链表的头节点
                head = tmp  # 移动到下一个节点
                group -= 1
            head = cur  # 当前反转组的最后一个节点更新为新头节点
        return head  # 返回新链表的头节点

示例运行

输入：

head = 1 -> 2 -> 3 -> 4 -> 5, k = 3

运行流程：

检查当前组是否有至少 K 个节点：
- 当前节点数为 3（满足条件），进入递归。
递归处理后续链表：
- 递归处理 4 -> 5 部分，因节点不足 3 个，保持原顺序返回。
反转当前组：
- 反转 1 -> 2 -> 3，连接到递归返回部分：
```
原始：1 -> 2 -> 3 -> 4 -> 5
反转：3 -> 2 -> 1 -> 4 -> 5
```
返回结果：
- 最终链表为：
```
3 -> 2 -> 1 -> 4 -> 5
```

时间复杂度分析

递归深度：
- 每次递归处理 K 个节点，共需 (O(n / k)) 次递归调用。
单次反转：
- 每组反转 K 个节点，时间复杂度为 (O(k))。

总时间复杂度为：
[
O(n)
]

空间复杂度分析

由于使用了递归，空间复杂度由递归栈决定：
[
O(n / k)
]

如果使用迭代实现，可将空间复杂度优化至 (O(1))。

示例输出

输入：

head = 1 -> 2 -> 3 -> 4 -> 5, k = 3

输出：

3 -> 2 -> 1 -> 4 -> 5

总结

反转 K 个一组的链表是一道经典的链表问题，它将递归和链表操作有机结合。通过递归的方式，我们能够高效地处理链表分组，并在每组内完成反转操作。

这种算法在工程中有广泛应用，例如处理数据块、实现批量任务的逆序等场景。理解这一问题不仅有助于提升算法能力，也是掌握链表操作的关键一步！

Post Views: 14

CODEBITWAVE