LeetCode 25. K 个一组翻转链表

Categories:

Tags:

题目描述
思路分析
1. 解法一：迭代法（推荐）
2. 解法二：递归法
复杂度分析
边界/坑点
要点小结
相似题目

题目描述

✅ 25. K 个一组翻转链表

题目：

给定链表的头节点 head，每 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) 额外内存空间的算法？

思路分析

解法一：迭代法（推荐）

核心思路：

先统计链表长度，判断是否还有足够 k 个节点可翻转。

用虚拟头节点 dummy 统一处理头部连接，每轮反转 [preGroupEnd.next, preGroupEnd.next+k)。

反转后将上一段尾部连接到新头，再把新尾连接到下一段起点。

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        // 统计链表长度
        int length = 0;
        ListNode cur = head;
        while (cur != null) {
            length++;
            cur = cur.next;
        }

        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode preGroupEnd = dummy;

        while (length >= k) {
            cur = preGroupEnd.next;
            // 记录本组翻转后的尾节点
            ListNode nextGroupStart = cur;

            ListNode pre = null;
            for (int i = 0; i < k; i++) {
                ListNode next = cur.next;
                cur.next = pre;
                pre = cur;
                cur = next;
            }

            // 连接：上一组末尾 -> 本组新头
            preGroupEnd.next = pre;
            // 连接：本组新尾 -> 下一组起点
            nextGroupStart.next = cur;

            preGroupEnd = nextGroupStart;
            length -= k;
        }

        return dummy.next;
    }
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	// 统计链表长度
	length := 0
	cur := head
	for cur != nil {
		length++
		cur = cur.Next
	}

	dummy := &ListNode{Next: head}
	preGroupEnd := dummy

	for length >= k {
		cur = preGroupEnd.Next
		// 记录本组翻转后的尾节点
		nextGroupStart := cur

		var pre *ListNode
		for i := 0; i < k; i++ {
			next := cur.Next
			cur.Next = pre
			pre = cur
			cur = next
		}

		// 连接：上一组末尾 -> 本组新头
		preGroupEnd.Next = pre
		// 连接：本组新尾 -> 下一组起点
		nextGroupStart.Next = cur

		preGroupEnd = nextGroupStart
		length -= k
	}

	return dummy.Next
}

解法二：递归法

核心思路：

先向前走 k 步，若不足 k 个节点直接返回原头。

反转 [head, tail) 区间，head 变为本组尾节点。

递归处理剩余链表并连接。

class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode tail = head;
        for (int i = 0; i < k; i++) {
            if (tail == null) {
                return head;
            }
            tail = tail.next;
        }

        // 反转 [head, tail) 区间
        ListNode newHead = reverse(head, tail);
        // 连接剩余部分
        head.next = reverseKGroup(tail, k);
        return newHead;
    }

    private ListNode reverse(ListNode head, ListNode tail) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != tail) {
            ListNode next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

func reverseKGroup(head *ListNode, k int) *ListNode {
	if head == nil || k == 1 {
		return head
	}

	tail := head
	for i := 0; i < k; i++ {
		if tail == nil {
			return head
		}
		tail = tail.Next
	}

	// 反转 [head, tail) 区间
	newHead := reverseRange(head, tail)
	// 连接剩余部分
	head.Next = reverseKGroup(tail, k)
	return newHead
}

func reverseRange(head *ListNode, tail *ListNode) *ListNode {
	var pre *ListNode
	cur := head
	for cur != tail {
		next := cur.Next
		cur.Next = pre
		pre = cur
		cur = next
	}
	return pre
}

复杂度分析

解法	时间复杂度	空间复杂度	适用场景/关键差异
解法一	O(n)	O(1)	严格 O(1) 空间，工程首选
解法二	O(n)	O(n/k)	代码简洁，但有递归栈开销

其中 n 为链表节点数。

边界/坑点

链表长度不足 k：剩余节点保持原顺序，迭代法的 length >= k 循环条件天然处理。
k == 1：每组只有一个节点，反转后不改变顺序，逻辑无异常。
迭代法中反转后本组新尾（原首节点）的 next 必须连接到下一组起点，顺序错误会断链。

要点小结

虚拟头节点 dummy 统一处理头部连接，消除第一组的边界特例。
迭代法先统计长度，循环每次翻转一组，翻转后维护 preGroupEnd 向后移动。
关键连接：反转后 preGroupEnd.next = pre（新头），nextGroupStart.next = cur（衔接下组）。
递归法直观，但 O(n/k) 栈深，迭代法是面试首选。

相似题目

题目	难度	考察点
24. 两两交换链表中的节点	中等	链表分组操作（k=2 特例）
1721. 交换链表中的节点	中等	链表双指针
2074. 反转偶数长度组的节点	中等	链表分组反转
206. 反转链表	简单	链表反转基础
92. 反转链表 II	中等	区间链表反转
143. 重排链表	中等	链表拆分+反转+合并
234. 回文链表	简单	链表反转后比较

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/67306654