K 个一组翻转链表

题目描述
给你链表的头节点 head，每 k 个节点一组进行翻转，并返回修改后的链表。

• k 是正整数，且小于或等于链表长度。
• 如果节点总数不是 k 的整数倍，请将最后剩余的节点保持原有顺序。

示例
输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

解题思路详解

1. 问题分析

• 链表需要按组翻转，每组长度为 k。
• 若剩余节点不足 k 个，则不翻转。
• 需要处理组与组之间的连接。

2. 核心步骤

1. 判断剩余节点是否足够 k 个：

   • 遍历 k 次，若遇到 null，说明不足 k 个，直接返回当前部分头节点。

2. 翻转当前组：

   • 使用迭代法翻转链表（类似反转链表题）。
   • 记录翻转后的新头（原组的尾节点）和新尾（原组的头节点）。

3. 连接前后组：

   • 将前一组的尾节点指向当前组翻转后的新头。
   • 当前组翻转后的新尾指向下一组的头（通过递归或迭代后续组）。

3. 递归实现（便于理解）

def reverseKGroup(head, k):
    # 步骤1：检查是否足够k个节点
    curr = head
    count = 0
    while curr and count < k:
        curr = curr.next
        count += 1
    if count < k:  # 不足k个，直接返回头节点
        return head
    
    # 步骤2：翻转当前k个节点
    prev = None
    curr = head
    for _ in range(k):
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    
    # 步骤3：连接后续组（递归处理剩余部分）
    head.next = reverseKGroup(curr, k)  # head现在是当前组的尾节点
    return prev  # prev是当前组翻转后的新头

4. 迭代实现（优化空间复杂度）

1. 使用哑节点（dummy node）简化头节点处理。
2. 维护两个指针：
   • group_prev：前一组的尾节点。
   • group_head：当前组的头节点。

def reverseKGroup(head, k):
    dummy = ListNode(0)
    dummy.next = head
    group_prev = dummy  # 前一组的尾节点
    
    while True:
        # 检查剩余节点是否足够k个
        curr = group_prev
        for _ in range(k):
            if not curr.next:
                return dummy.next
            curr = curr.next
        group_head = group_prev.next  # 当前组头节点
        
        # 翻转当前组（迭代法）
        prev, curr = None, group_head
        for _ in range(k):
            next_temp = curr.next
            curr.next = prev
            prev = curr
            curr = next_temp
        
        # 连接前后组
        group_prev.next = prev  # 前一组的尾指向当前组的新头
        group_head.next = curr  # 当前组的新尾指向下一组的头
        group_prev = group_head  # 更新前一组的尾为当前组的新尾

5. 关键细节

• 哑节点的作用：避免对头节点的特殊处理。
• 连接逻辑：翻转后，原组头节点变成新尾，需指向下一组的头。
• 边界处理：k=1 时无需翻转，直接返回原链表。

复杂度分析

• 时间复杂度：O(n)，每个节点被访问两次。
• 空间复杂度：
  • 递归：O(n/k)（递归栈深度）。
  • 迭代：O(1)。