Bloomberg 面试题：将带「向下指针」的多层链表展开成一条普通链表

题目描述

给定一个多层链表，每个节点除了有 next 指针外，还可能有一个 down 指针指向另一层链表。要求将这个多层链表"展开"成一条单层链表，展开规则是：将每个节点的 down 链插入到该节点和其 next 节点之间。

示例

原始结构：
Top level: [1] -> [2] -> [3] -> [8] -> [10]
                          |             |
                          v             v
                         [4] -> [5] -> [6]    [9]
                                        |
                                        v
                                       [7]

展开后：
[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] -> [10]

解题思路

这道题可以用递归或栈来解决：

1. 遍历链表，遇到有 down 指针的节点时
2. 保存当前节点的 next
3. 递归（或用栈）处理 down 链
4. 将处理后的 down 链接到当前节点后面
5. 找到 down 链的尾部，连接之前保存的 next

Python 实现

class Node:
    def __init__(self, val, next=None, down=None):
        self.val = val
        self.next = next
        self.down = down

def flatten(head: Node) -> Node:
    if not head:
        return None
    
    curr = head
    while curr:
        if curr.down:
            # 保存原来的 next
            next_node = curr.next
            
            # 递归展开 down 链
            down_head = flatten(curr.down)
            
            # 将 down 链接到当前节点后
            curr.next = down_head
            curr.down = None
            
            # 找到 down 链的尾部
            tail = down_head
            while tail.next:
                tail = tail.next
            
            # 连接原来的 next
            tail.next = next_node
        
        curr = curr.next
    
    return head

使用栈的迭代解法

def flatten_iterative(head: Node) -> Node:
    if not head:
        return None
    
    stack = []
    curr = head
    
    while curr:
        if curr.down:
            if curr.next:
                stack.append(curr.next)
            curr.next = curr.down
            curr.down = None
        
        if not curr.next and stack:
            curr.next = stack.pop()
        
        curr = curr.next
    
    return head

复杂度分析

• 时间复杂度：O(n)，每个节点只访问一次
• 空间复杂度：O(d)，d 是最大嵌套深度（递归调用栈）

面试要点

1. 确认展开顺序：down 链是插入到当前节点后还是 next 节点前
2. 处理多层嵌套：down 链中的节点也可能有自己的 down
3. 边界情况：空链表、只有一个节点、没有 down 的链表

需要面试辅助服务？联系我们

• 📧 Email: [email protected]
• 📱 Phone: +86 17863968105

需要面试真题？ 立刻联系微信 Coding0201，获得真题。