如何正确理解算法空间复杂度？K个一组翻转链表复杂度分析

我正在求解LeetCode上的K个一组翻转链表题目，编写了如下可正常运行的翻转功能实现代码：

package com.sample.testapp

class LinkedListPractice {
    class ListNode(val data: Int) {
        var next: ListNode? = null
    }
    companion object {
        @JvmStatic
        fun main(args: Array<String>) {

            var root: ListNode = ListNode(1)
            root.next = ListNode(2)
            root.next!!.next = ListNode(3)
            root.next!!.next?.next = ListNode(4)
            root.next!!.next?.next?.next = ListNode(5)
            println("Initial")
            prinLinkedList(root)

            var k = 2
            val answer = reverseKNodes(root, k)
            println()
            println("After reverse")
            prinLinkedList(answer)

        }

        fun prinLinkedList(root: ListNode?) {
            var current = root
            while (current != null) {
                print(current.data)
                current = current.next
                print("->")
            }
        }

        private fun reverseKNodes(root: ListNode?, k: Int): ListNode? {
            if (root == null) return null
            //reverse first k nodes and then call for next recursively until linkedlist ends
            var counter = 0
            var pre: ListNode? = null
            var next: ListNode? = null
            var current = root
            while (current != null && counter < k) {
                next = current?.next
                current?.next = pre
                pre = current
                current = next
                counter++
            }
            if (next != null) {
                root.next = reverseKNodes(next, k)
            }
            return pre
        }
    }
}

核心疑问 #

计算该程序的空间复杂度时我存在两个矛盾的判断：

• 最初理解：代码中仅创建了指向节点的指针完成翻转操作，没有新建链表节点，空间复杂度应为常数级O(1)
• 疑问点1：代码中声明的pre、next这类引用变量被赋值时，是否会产生额外空间占用？
• 疑问点2：遍历所有K分组的过程中，每次递归调用都会创建新的pre等局部变量，这种情况下算法空间复杂度是否应为O(N)？

解答 #

先直接给结论：你当前写的递归实现，空间复杂度是O(N/K)，在常规题设下（K为固定常数，和输入链表长度N无关），等价于O(N)；只有改成纯迭代实现、消除递归栈开销时，才能做到O(1)的额外空间复杂度。

针对你的两个疑问逐一澄清：

1. 单次函数内的pre、next、current、counter这类局部变量，本身只占固定大小的空间：这些变量只是指向原有链表节点的引用，不会复制或新建链表节点，单个函数调用里这些变量的总占用是常数，不会随输入规模增长。
2. 真正带来线性空间开销的是递归调用栈，而不是单个的pre/next变量：
   每处理完一组K个节点，你的代码就会递归调用一次reverseKNodes处理下一组，每一次递归调用都会在程序的调用栈上压入一个新的栈帧，栈帧里保存了当前函数的所有局部变量、返回地址等信息，这些栈帧只有等下层递归返回后才会被弹出释放。
   总递归深度等于链表被分成的K组数量，也就是⌈N/K⌉：
   • 当K是固定常数（比如你示例里的k=2），递归深度和链表长度N成正比，总栈空间随N线性增长，空间复杂度为O(N)
   • 极端情况k=1（每个节点自己为一组翻转，相当于链表不变），递归深度等于N，空间复杂度明确为O(N)
   • 极端情况k=N（整段链表一次翻转），递归深度为1，这时候空间复杂度才是O(1)

注意：算法空间复杂度统计的是输入数据之外的所有额外辅助空间，调用栈占用的空间属于必须统计的辅助空间，不能因为没有在堆上新建节点就忽略这部分开销。

如果要实现O(1)额外空间的K组翻转，需要把递归逻辑改成迭代实现：提前遍历统计链表长度确定总组数，用哑节点记录新链表头，每一组用循环翻转后拼接前后节点，全程只维护固定数量的指针变量，不产生递归栈开销。

内容的提问来源于stack exchange，提问作者Nayab