Medium

题目描述

给你一个基于双向链表的多级数据结构，链表中的节点除了有 next 和 prev 指针外，还有一个 child 指针，该指针可能指向单独的双向链表，也包含这些特殊的节点。这些子链表可能还有自己的一个或多个子链表，以此类推，生成多级数据结构。

给定第一级的链表头节点，请扁平化链表，使所有节点出现在单级的双向链表中。设有子链表的节点为 curr，子链表中的节点应该出现在扁平化列表中的 curr 之后和 curr.next 之前。

返回扁平化后的链表的头节点。链表中的节点必须将其 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]

示例 2：

输入：head = [1,2,null,3]
输出：[1,3,2]

示例 3：

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

约束条件：

  • 节点数目不超过 1000
  • 1 <= Node.val <= 10^5

解题思路

这道题要求将多级双向链表扁平化为单级链表。核心思路是遇到有子链表的节点时，需要将子链表插入到当前节点和下一个节点之间。

解法分析：

  1. 深度优先搜索（DFS）递归法：递归处理每个子链表，返回子链表的尾节点，便于连接后续节点。

  2. 迭代+栈法：使用栈保存遇到子链表时的下一个节点，优先处理子链表，处理完后再处理栈中保存的节点。

  3. 原地迭代法（推荐）：直接在原链表上操作，遇到子链表时立即插入，无需额外空间。

推荐解法思路： 遍历链表，当遇到有 child 的节点时：

  1. 保存当前节点的 next 指针
  2. 将 child 插入到当前节点后面
  3. 找到子链表的尾节点
  4. 将原来保存的 next 节点连接到子链表尾部
  5. 清空 child 指针

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)，是最优解法。

代码实现

class Solution {
public:
    Node* flatten(Node* head) {
        if (!head) return head;
        
        Node* curr = head;
        while (curr) {
            if (curr->child) {
                Node* next = curr->next;
                Node* child = curr->child;
                
                // 连接当前节点和子链表
                curr->next = child;
                child->prev = curr;
                curr->child = nullptr;
                
                // 找到子链表的尾节点
                Node* tail = child;
                while (tail->next) {
                    tail = tail->next;
                }
                
                // 连接子链表尾部和原来的下一个节点
                if (next) {
                    tail->next = next;
                    next->prev = tail;
                }
            }
            curr = curr->next;
        }
        
        return head;
    }
};

class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return head
        
        curr = head
        while curr:
            if curr.child:
                next_node = curr.next
                child = curr.child
                
                # 连接当前节点和子链表
                curr.next = child
                child.prev = curr
                curr.child = None
                
                # 找到子链表的尾节点
                tail = child
                while tail.next:
                    tail = tail.next
                
                # 连接子链表尾部和原来的下一个节点
                if next_node:
                    tail.next = next_node
                    next_node.prev = tail
            
            curr = curr.next
        
        return head

public class Solution {
    public Node Flatten(Node head) {
        if (head == null) return head;
        
        Node curr = head;
        while (curr != null) {
            if (curr.child != null) {
                Node next = curr.next;
                Node child = curr.child;
                
                // 连接当前节点和子链表
                curr.next = child;
                child.prev = curr;
                curr.child = null;
                
                // 找到子链表的尾节点
                Node tail = child;
                while (tail.next != null) {
                    tail = tail.next;
                }
                
                // 连接子链表尾部和原来的下一个节点
                if (next != null) {
                    tail.next = next;
                    next.prev = tail;
                }
            }
            curr = curr.next;
        }
        
        return head;
    }
}

var flatten = function(head) {
    if (!head) return head;
    
    let curr = head;
    while (curr) {
        if (curr.child) {
            let next = curr.next;
            let child = curr.child;
            
            // 连接当前节点和子链表
            curr.next = child;
            child.prev = curr;
            curr.child = null;
            
            // 找到子链表的尾节点
            let tail = child;
            while (tail.next) {
                tail = tail.next;
            }
            
            // 连接子链表尾部和原来的下一个节点
            if (next) {
                tail.next = next;
                next.prev = tail;
            }
        }
        curr = curr.next;
    }
    
    return head;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(n)
空间复杂度O(1)

其中 n 为链表中节点的总数。每个节点最多被访问两次（一次遍历，一次找尾节点），所以时间复杂度为 O(n)。算法只使用了常数个额外变量，空间复杂度为 O(1)。

相关题目