当前位置：首页 > article >正文

LeetCode 25 - K 个一组翻转链表

article 2025/3/5 4:48:04

LeetCode 25 - K 个一组翻转链表

这道题是一个典型的链表操作题，考察我们对链表的精确操作，包括反转链表、分组处理、递归和迭代的结合应用等。还可以通过变体问题延伸到优先队列操作、归并、分块等，这使得它成为面试中的高频考题之一。

题目描述

给你一个链表，每 k 个节点一组进行翻转，并返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余节点保持原样。
你不允许更改节点的值，只能调整节点指针的方向。

示例

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

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

解题思路与分析

核心简化问题

分段处理链表：将链表分成每 k 个一组。
对每一组执行反转操作。
当遍历到不足 k 个节点的部分时，维持原顺序不再反转。
方法可以通过递归或迭代完成。

解法与代码模板

解法 1：递归法

核心思路

使用递归配合局部反转：
1. 确定链表是否有足够的 k 个节点：如果不足 k 个，直接返回头节点。
2. 如果有足够的 k 个节点：
  - 完成当前组内 k 个节点的反转，
  - 递归地对剩余部分链表继续处理。
3. 将当前反转的部分连接到下一组递归结果。

模板代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 检查链表是否有足够的 k 个节点
        ListNode current = head;
        int count = 0;
        while (current != null && count < k) {
            current = current.next;
            count++;
        }

        // 如果不足 k 个节点，直接返回原链表
        if (count < k) {
            return head;
        }

        // 反转当前 k 个节点
        ListNode prev = null, next = null;
        current = head;

        for (int i = 0; i < k; i++) {
            next = current.next;   // 暂存下一节点
            current.next = prev;  // 改变指针方向
            prev = current;       // 移动 prev 指针
            current = next;       // 移动 current 指针
        }

        // 递归处理剩余链表，并连接反转后的部分
        head.next = reverseKGroup(current, k);

        // 返回反转后的头节点
        return prev;
    }
}

复杂度分析

时间复杂度: O(N)
- 每个节点仅访问一次。
空间复杂度: O(N / k)
- 递归调用栈的深度为 (链表长度 / k)。

优缺点

优点:代码简洁并且逻辑清晰，适合递归思路的场景。
缺点:会造成大量递归栈调用，链表很长时可能出现栈溢出。

解法 2：迭代法

核心思路

相对于递归法，用迭代来实现分组反转链表，避免了递归栈空间的开销：
1. 使用 哑结点（dummy node）作为新链表的起始位置，方便连接。
2. 遍历链表，分别找到每一组的起始结点和结束结点。
3. 将当前分组进行反转，并连接到已经处理好的链表部分。
4. 当剩余节点不足时，停止反转，直接连接到尾部。

模板代码

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 创建哑结点
        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        ListNode prevGroupEnd = dummy;

        while (true) {
            // 找到当前组的开始和结束节点
            ListNode groupStart = prevGroupEnd.next;
            ListNode groupEnd = prevGroupEnd;
            for (int i = 0; i < k; i++) {
                groupEnd = groupEnd.next;
                if (groupEnd == null) {
                    return dummy.next; // 不足 k 个节点
                }
            }

            // 下一组的起始节点
            ListNode nextGroupStart = groupEnd.next;

            // 反转当前组
            reverseList(groupStart, groupEnd);

            // 连接反转后的部分
            prevGroupEnd.next = groupEnd; // 当前组的结尾变成起始点
            groupStart.next = nextGroupStart;

            // 更新 prevGroupEnd 为这一组的最后节点
            prevGroupEnd = groupStart;
        }
    }

    private void reverseList(ListNode start, ListNode end) {
        ListNode prev = null, current = start, next = null;
        ListNode stop = end.next; // 保存停止位置

        while (current != stop) {
            next = current.next;
            current.next = prev;
            prev = current;
            current = next;
        }
    }
}

复杂度分析

时间复杂度: O(N)
- 每个节点最多被访问两次（反转和连接）。
空间复杂度: O(1)
- 没有额外栈空间的使用，仅需常数级别指针。

优缺点

优点: 比递归方法更高效，适用于超长链表。
缺点: 实现逻辑上稍微复杂。

解法 3：栈辅助法

核心思路

借助栈来反转每一组节点：
1. 遍历链表，将 k 个节点压入栈中。
2. 当栈中节点数量达到 k 时，出栈并重新连接节点指针。
3. 如果节点数量不足 k，直接连接剩余部分。

模板代码

import java.util.Stack;

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if (head == null || k <= 1) return head;

        Stack<ListNode> stack = new Stack<>();
        ListNode dummy = new ListNode(-1);
        ListNode prev = dummy;
        dummy.next = head;

        while (head != null) {
            // 将 k 个节点压入栈
            for (int i = 0; i < k && head != null; i++) {
                stack.push(head);
                head = head.next;
            }

            // 判断栈中是否有足够的 k 个节点
            if (stack.size() == k) {
                // 出栈并重新连接
                while (!stack.isEmpty()) {
                    prev.next = stack.pop();
                    prev = prev.next;
                }
                prev.next = head; // 连接当前组与下一组
            }
        }

        return dummy.next;
    }
}