LeetCode 第430题：扁平化多级双向链表

📖 文章摘要

本文详细解析LeetCode第430题“扁平化多级双向链表”，这是一道考察链表操作和递归的问题。文章提供了基于DFS的解题思路，包含C#、Python、C++三种语言实现，配有详细的分析和性能对比。适合想要提升链表操作和递归思维能力的程序员。

核心知识点： 双向链表、递归、DFS
难度等级： 中等
推荐人群： 具有基础数据结构知识的程序员

题目描述

你会得到一个双向链表，其中包含的节点有一个下一个指针、一个前一个指针和一个额外的子指针。这个子指针可能指向一个单独的双向链表，也包含这些特殊的节点。这些子列表可能有一个或多个自己的子项，以此类推，形成多级数据结构。

给定链表的头节点 head ，将链表扁平化，使所有节点都出现在单级双链表中。让 curr 是一个带有子列表的节点。子列表中的节点应该出现在扁平化列表中的 curr 之后和 curr.next 之前。

返回扁平列表的 head 。列表中的节点必须将其所有子指针设置为 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]
解释：输入的多级列表如下图所示：

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]
解释：输入的多级列表如下图所示：
  1---2---NULL
  |
  3---NULL

示例 3：

输入：head = []
输出：[]

提示

节点数目不超过 1000
1 <= Node.val <= 105

解题思路

本题可以使用深度优先搜索（DFS）来解决，主要步骤如下：

遍历主链表：
- 记录当前节点
- 保存next指针
处理子链表：
- 递归处理子链表
- 将子链表与主链表连接
恢复连接：
- 连接子链表的最后一个节点与原next节点
- 清除child指针

图解思路

扁平化过程分析

步骤	操作	结果	说明
初始状态	-	多级链表	原始链表结构
遍历主链表	找到带子链表的节点	定位子链表	准备处理子链表
处理子链表	递归扁平化	扁平子链表	子链表变为单层
连接操作	合并链表	完整单层链表	最终扁平结构

指针操作示意

阶段	prev指针	next指针	child指针	说明
开始	正常连接	正常连接	指向子链表	初始状态
子链表处理	更新连接	保存原next	处理子链表	处理中间状态
完成	全部连接	全部连接	置为null	最终状态

代码实现

C# 实现

public class Solution {
    public Node Flatten(Node head) {
        if (head == null) return null;
        
        // 使用DFS扁平化链表
        FlattenDFS(head);
        return head;
    }
    
    private Node FlattenDFS(Node node) {
        if (node == null) return null;
        
        // 保存当前节点的next
        Node next = node.next;
        
        // 如果有子链表，先处理子链表
        if (node.child != null) {
            Node child = node.child;
            
            // 连接当前节点和子链表
            node.next = child;
            child.prev = node;
            node.child = null;
            
            // 获取扁平化后的子链表的最后一个节点
            Node last = FlattenDFS(child);
            
            // 如果原来的next不为空，连接它
            if (next != null) {
                last.next = next;
                next.prev = last;
            }
            
            // 返回处理后的最后一个节点
            return next == null ? last : FlattenDFS(next);
        }
        
        // 如果没有子链表，继续处理next
        return next == null ? node : FlattenDFS(next);
    }
}

Python 实现

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        if not head:
            return None
        
        # 扁平化函数
        def flatten_dfs(node):
            if not node:
                return None
            
            # 保存当前节点的next
            next_node = node.next
            
            # 如果有子链表，先处理子链表
            if node.child:
                child = node.child
                
                # 连接当前节点和子链表
                node.next = child
                child.prev = node
                node.child = None
                
                # 获取扁平化后的子链表的最后一个节点
                last = flatten_dfs(child)
                
                # 如果原来的next不为空，连接它
                if next_node:
                    last.next = next_node
                    next_node.prev = last
                
                # 返回处理后的最后一个节点
                return flatten_dfs(next_node) if next_node else last
            
            # 如果没有子链表，继续处理next
            return flatten_dfs(next_node) if next_node else node
        
        flatten_dfs(head)
        return head

C++ 实现

class Solution {
public:
    Node* flatten(Node* head) {
        if (!head) return nullptr;
        
        // 使用DFS扁平化链表
        flattenDFS(head);
        return head;
    }
    
private:
    Node* flattenDFS(Node* node) {
        if (!node) return nullptr;
        
        // 保存当前节点的next
        Node* next = node->next;
        
        // 如果有子链表，先处理子链表
        if (node->child) {
            Node* child = node->child;
            
            // 连接当前节点和子链表
            node->next = child;
            child->prev = node;
            node->child = nullptr;
            
            // 获取扁平化后的子链表的最后一个节点
            Node* last = flattenDFS(child);
            
            // 如果原来的next不为空，连接它
            if (next) {
                last->next = next;
                next->prev = last;
            }
            
            // 返回处理后的最后一个节点
            return next ? flattenDFS(next) : last;
        }
        
        // 如果没有子链表，继续处理next
        return next ? flattenDFS(next) : node;
    }
};

执行结果

C# 实现

执行用时：88 ms
内存消耗：37.2 MB

Python 实现

执行用时：36 ms
内存消耗：15.1 MB

C++ 实现

执行用时：4 ms
内存消耗：7.4 MB

性能对比

语言	执行用时	内存消耗	特点
C#	88 ms	37.2 MB	实现清晰但性能较差
Python	36 ms	15.1 MB	代码简洁，性能中等
C++	4 ms	7.4 MB	性能最优

代码亮点

🎯 使用DFS优雅处理多级结构
💡 巧妙保存和恢复链表连接
🔍 高效的指针操作
🎨 代码结构清晰，易于维护

常见错误分析

🚫 未正确处理空节点
🚫 忘记清除child指针
🚫 指针连接顺序错误
🚫 递归返回值处理不当

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
DFS递归	O(n)	O(n)	实现简单，直观	递归栈开销
迭代	O(n)	O(1)	空间复杂度低	实现复杂

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第430题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

示例 3：

提示

解题思路

图解思路

扁平化过程分析

指针操作示意

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流