K 个一组翻转链表

GitHub跳转原题关系图返回列表

先找第 k 个节点，翻转这一段并接回；不足 k 段保持原样。

OJ: leetcodecn

题目 ID: reverse-nodes-in-k-group

难度:提高+/省选-

标签:链表递归cpppython

日期: 2026-07-28 22:05

目录

  1. 题意
  2. 思路
  3. 代码
  4. 复杂度
  5. 总结

题意

每 k 个节点一组翻转链表，不足 k 的保持原样。

思路

递归版：先检查是否有 k 个节点，有则递归处理后续部分，再翻转当前段。迭代版更节省空间：用 dummy 和 prev 指针维护已翻转到未处理的边界，每轮找到第 k 个节点后翻转段内指针。

代码

cpp
/**
 * Author by Rainboy
 */
// main.cpp：先找第 k 个节点，翻转这一段并接回；不足 k 段保持原样。
#include <bits/stdc++.h>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;

    ListNode(int x) : val(x), next(nullptr) {}
};

class Solution {
public:
    ListNode *reverseKGroup(ListNode *head, int k) {
        ListNode dummy(0);
        dummy.next = head;
        auto prev = &dummy;
        while (true) {
            auto end = prev;
            for (int i = 0; i < k && end; i++)
                end = end->next;
            if (!end)
                break;
            auto start = prev->next, nxt = end->next;
            auto a = start, b = a->next;
            while (b != nxt) {
                auto c = b->next;
                b->next = a;
                a = b;
                b = c;
            }
            start->next = nxt;
            prev->next = a;
            prev = start;
        }
        return dummy.next;
    }
};

ListNode *build(istream &in, int n) {
    if (!n)
        return nullptr;
    auto head = new ListNode(0), cur = head;
    for (int i = 0, v; i < n; i++) {
        in >> v;
        cur->next = new ListNode(v);
        cur = cur->next;
    }
    return head->next;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    cin >> n >> k;
    auto head = build(cin, n);
    head = Solution().reverseKGroup(head, k);
    for (auto p = head; p; p = p->next)
        cout << p->val << ' ';
    return 0;
}
python
#!/usr/bin/env python3
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None


class Solution:
    def reverseKGroup(self, head: ListNode, k: int) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        while True:
            end = prev
            for _ in range(k):
                end = end.next
                if not end:
                    return dummy.next
            start = prev.next
            nxt = end.next
            a, b = start, start.next
            while b is not nxt:
                c = b.next
                b.next = a
                a = b
                b = c
            start.next = nxt
            prev.next = a
            prev = start


def build(arr):
    dummy = cur = ListNode(0)
    for v in arr:
        cur.next = ListNode(v)
        cur = cur.next
    return dummy.next


def main() -> None:
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    head = build(a)
    head = Solution().reverseKGroup(head, k)
    while head:
        print(head.val, end=" ")
        head = head.next


if __name__ == "__main__":
    main()

复杂度

  • 时间复杂度：O(n)。
  • 空间复杂度：O(1) 迭代，O(n/k) 递归。

总结

K 个一组翻转是链表操作的综合练习，需要同时处理"寻找段尾"、“段内翻转”、"衔接前后"三个子任务。