Leetcode題解 Python：Flatten a Multilevel Doubly Linked List

給一串 Doubly Linked List ，其中某節可能有 child ，要求你把這串 Doubly Linked List 平坦化，而 child 會插入在 該節 與 下一節 之間。

A – B – C – D – E        => A – B – F – G – C – D – E
      F  – G

寫一個遞迴函數，如果遇到 child ，你需要它的頭尾，針對這兩點修改就好。
(尾)G.next = B.next,  G.next.prev = G 、B.next = F(頭) , B.next.prev = B

於是遞迴函數的回傳值，就設定是 head 與 tail。

頭是搜尋的起點，有頭才能夠搜尋，而尾在尚未搜尋前是未知的，於是遞迴函數的回入值是頭節。

這樣在一路到底搜尋時，若是碰到 child，則把 child node 傳給遞迴函數，取得該子串的頭尾，然後插入當前的位置與下一位置的中間。

空間複雜度為 O(1)

class Solution:
    def flatten(self, head: 'Node') -> 'Node':
        def nextNode(node):
            head = tail = node            
            while tail:
                if tail.child:
                    ch, ct = nextNode(tail.child)
                    if tail.next:
                        ct.next = tail.next
                        ct.next.prev = ct
                    tail.next = ch
                    tail.next.prev = tail
                    tail.child = None
                    tail = ct                   
                else:
                    if tail.next:
                        tail = tail.next
                    else:
                        break            
            return head, tail            
        return nextNode(head)[0]

另外一種則是先遍歷，記錄順序，最後再重組。

class Solution:    
    def flatten(self, head: 'Node') -> 'Node':
        nodes = []
        def nextNode(node):
            if node:
                nodes.append(node)
                nextNode(node.child)                
                nextNode(node.next)
        nextNode(head)
        p = None
        for each in nodes:
            each.child = None
            each.prev = p
            if p: p.next = each
            p = each
        return head