Bloomberg 面試題：將帶「向下指標」的多層鏈結串列展開

題目描述

給定一個多層鏈結串列，每個節點除了 next 指標外，還可能有 down 指標指向下一層鏈表。

目標：把整個結構展開成單層鏈結串列。展開規則是：把每個節點的 down 鏈，插入到該節點與原本 next 之間，並保留相對順序。

範例

展開前：

[1] -> [2] -> [3] -> [8] -> [10]
              |
              v
             [4] -> [5] -> [6]
                          |
                          v
                         [7]

[8] 也有 down：
[8]
 |
 v
[9]

展開後：

[1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] -> [10]

解題思路

常見兩種做法：

• 遞迴：遇到 down 先展開子鏈，接到當前節點後，再把原本的 next 接回去。
• 堆疊：遇到 down 先把 next 暫存到 stack，優先走 down；走到底再 pop 回來繼續。

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_node = curr.next
            down_head = flatten(curr.down)
            curr.next = down_head
            curr.down = None

            tail = down_head
            while tail and tail.next:
                tail = tail.next
            if tail:
                tail.next = next_node

        curr = curr.next

    return head

Python（堆疊）

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)（遞迴深度或 stack 深度）

需要面試輔助服務？聯絡 OA VO Service

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

需要面試真題？ 立刻聯繫微信 Coding0201，獲得真題。