求扁平化多级双向链表解法的最坏时间复杂度

问题背景 #

我正在解决LeetCode上的「扁平化多级双向链表」问题，问题描述如下：

给定一个多级双向链表，链表中的节点包含next指针、prev指针以及额外的child指针。该child指针可能指向另一个多级双向链表，且子链表也可能拥有自己的子链表，以此形成多级数据结构。
给定链表第一层的head节点，将该链表扁平化为单级双向链表。若curr节点存在子链表，则子链表的节点应出现在curr节点之后、curr.next节点之前。返回扁平化后的链表head，且所有节点的child指针需设为null。

示例1：

• 输入：head = [1,2,3,4,5,6,null,null,null,7,8,9,10,null,null,11,12]
• 输出：[1,2,3,7,8,11,12,9,10,4,5,6]

我的解法 #

class Solution {
    public Node flatten(Node head) {
        if(head == null) {
            return head;
        }
        
        Node curr = head;
        Node prev = curr.prev;
        Node next = curr.next;

        while(curr != null) {
            if(curr.child != null) {
                Node child = flatten(curr.child);
                // 获取子链表的尾节点
                while(child.next != null) {
                    child = child.next;
                }
                Node tail = child;
                curr.next = curr.child;
                curr.child.prev = curr;
                tail.next = next;
                if(next != null) {
                    next.prev = tail;
                }
                curr.child = null;
            }
            // 移动到下一个节点
            prev = next != null ? next.prev : curr;
            curr = next;
            next = next != null ? next.next : null;
        }

        return head;
    }
}

我的疑问 #

这个解法的最坏时间复杂度是多少？
我注意到每次处理child时，都需要遍历子链表来获取其尾节点，我猜测当所有节点都有子节点时情况会很差，但不知道如何推导具体的时间复杂度。比如以下两种极端情况：

1 <-> 2 <-> 3 <-> 4
|     |     |     |
5     6     7     8
|     |     |     |
9     10    11    12
|     |     |     |
13    14    15    16

1 <-> 2 <-> 3 <-> 4 ...
|     |     |     |
5     6     7     8 <-> 17 <-> 19
|     |     |     |      |      |
9     10    11    12    18     20 ...
|     |     |     |      .      .
13    14    15    16     .      .

时间复杂度分析 #

你的解法的最坏时间复杂度是O(n²)，其中n是链表的总节点数，推导过程如下：

1. 核心开销点：每次遇到带child的节点时，你会先递归扁平化子链表，然后遍历整个子链表找到尾节点——这一步的时间开销是子链表的节点数k，即O(k)。

2. 最坏场景构造：考虑一种极端结构：每个节点的child指向一个单链的子链表，且整个多级结构形成一个类似"链式嵌套"的形态，比如：

   1 -> child -> 2 -> child -> 3 -> child -> ... -> n
   

   这种结构下，总节点数是n。

3. 开销累加计算：

   • 处理节点1时，递归扁平化2到n的子链表，然后遍历2到n找尾，开销为O(n-1)；
   • 处理节点2时，递归扁平化3到n的子链表，然后遍历3到n找尾，开销为O(n-2)；
   • ...
   • 处理节点n-1时，递归扁平化节点n，然后遍历节点n找尾，开销为O(1)；
   • 总开销为：(n-1)+(n-2)+...+1 = n(n-1)/2，这属于O(n²)的时间复杂度。

4. 你举的例子验证：第一个例子总节点数16，总遍历开销为43 + 42 +4*1 = 24，而16²=256，24是O(n²)范围内的量级；当节点数持续增大时，总开销会呈现平方级增长。

简单来说，因为每个节点可能被多次遍历（作为子链表的节点被上层节点的找尾循环访问），最坏情况下总遍历次数是节点数的平方级。

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