LeetCode-25 K 个一组翻转链表

题目描述

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

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

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

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

示例 2：

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

提示：

• 链表中的节点数目为 n
• 1 <= k <= n <= 5000
• 0 <= Node.val <= 1000

进阶：你可以设计一个只用 O(1) 额外内存空间的算法解决此问题吗？

题解

方法一：栈辅助法（O(k) 空间）

解题思路

利用栈的“先进后出”特性实现翻转：

1. 遍历链表：将每组的 k 个节点依次压入栈中。
2. 栈满翻转：当栈中元素达到 k 个时，依次弹出并连接到前一组的末尾。
3. 处理剩余节点：若最后剩余不足 k 个节点，直接连接剩余节点。

代码实现

# 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[ListNode], k: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        pre = dummy
        stack = []
        p = head

        while p:
            stack.append(p)
            p = p.next
            # 栈满进行交换
            if len(stack) == k:     
                while stack:
                    pre.next = stack.pop()
                    pre = pre.next
                pre.next = None
        
        # 处理剩余节点
        if stack:
            pre.next = stack[0]
            
        return dummy.next

复杂度分析

• 时间复杂度：O(n)，每个节点入栈、出栈各一次。
• 空间复杂度：O(k)，栈存储最多 k 个节点。

---

方法二：直接翻转法（O(1) 空间）

解题思路

直接在链表上操作指针，无需额外空间：

1. 分组定位：找到每组的起始节点 start 和结束节点 end。
2. 组内翻转：翻转当前组的 k 个节点，并记录下一组的起始节点。
3. 连接链表：将翻转后的子链表与前后的链表正确连接。

代码实现

class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
        def reverse(start, end):
            # 翻转从 start 到 end 的链表
            prev, curr = None, start
            while curr != end:
                next_node = curr.next
                curr.next = prev
                prev = curr
                curr = next_node
            return prev  # 返回翻转后的头节点

        dummy = ListNode(next=head)
        pre = dummy
        while True:
            # 找到当前组的起始节点和结束节点
            start = pre.next
            end = pre
            for _ in range(k):
                end = end.next
                if not end:  # 如果不足 k 个节点，直接返回
                    return dummy.next
            
            # 记录下一组的起始节点
            next_group = end.next
            
            # 翻转当前组
            new_start = reverse(start, next_group)
            
            # 将翻转后的组连接到前面的链表
            pre.next = new_start
            start.next = next_group
            
            # 更新 pre 指针
            pre = start
        
        return dummy.next

复杂度分析

• 时间复杂度：O(n)，每个节点被遍历和翻转一次。
• 空间复杂度：O(1)，仅使用常数级变量。

---

方法对比

方法	优点	缺点	适用场景
栈辅助法	逻辑简单，易实现	空间复杂度为 O(k)	k 较小时
直接翻转法	空间最优O(1)	指针操作较复杂	内存敏感的场景

---

总结

• 栈辅助法适合快速实现，但空间开销随 k 增大而增加。
• 直接翻转法是更优解，通过指针操作直接在链表上完成翻转，空间复杂度为常数。
• 两种方法均需注意边界条件，如链表长度不足 k 时的处理。