在 Python 中展平多级双向链表

Question

我正在研究 LeetCode 问题 430. Flatten a Multilevel Doubly Linked List:

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.

Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.

Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.

我的方法

这是我打算做的：

遍历头节点，凡出现子节点的地方，将当前节点的link改为子节点
然后，将遍历的所有节点添加到一个单独的LList中（在我的代码中是ll）。我将 dummy 保留在新 LList 的开头。
在到达每个子节点时，将该节点地址添加到堆栈中。所以，当做pop()操作时，最后添加的子节点将首先被检索。
之后，弹出并遍历该子节点直到 None 并将新节点添加到新的 LList，即 ll。最后，returndummy.next

我的代码

class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        curr = head
        ll = dummy = ListNode(0)
        stack = []
        
        while curr:
            if curr.child:
                stack.append(curr)
                ll.next = curr
                curr.next = curr.child
            else:
                ll.next = curr
            ll = ll.next
            curr = curr.next
        
        while stack:
            curr_node = stack.pop()
            
            while curr_node:
                ll.next = curr_node
                ll = ll.next
                curr_node = curr_node.next
        return dummy.next

问题

我收到了超出时间限制的警告。有人可以告诉我我的方法是否正确以及哪里出错了吗？

Answer 1

代码的第二部分是在 ll 列表中创建一个循环。您从堆栈中弹出的节点在您将节点推入堆栈时已经放入 ll 列表中。但是你再次将它追加到 ll 列表中，形成一个循环。所以 while curr_node: 变成了一个无限循环。

尽管算法的总体思路很好，但是将 next 节点而不是 current 节点压入堆栈。

此外，您应该：

处理完后清除 child 引用
改编prev参考资料，使其与next参考资料的部分改动保持一致。请记住：这是一个双向链表，您需要 return.

我不会：

落后于单独的 ll 参考。您可以只使用 curr
使用dummy节点。虽然我明白它的用处，但是一旦你处理了空列表的情况（作为边界情况），就真的没有任何好处了

所以我会这样做：

class Solution:
    def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return
        stack = []
        current = head
        while current:
            if current.child:
                if current.next:
                    stack.append(current.next)
                current.next = current.child
                current.next.prev = current
                current.child = None
            elif not current.next and stack:
                current.next = stack.pop()
                current.next.prev = current
            current = current.next
        return head

在 Python 中展平多级双向链表

Flatten a multilevel doubly LinkedList in Python

python-3.x

doubly-linked-list

我的方法

我的代码

问题