剑指 Offer II 028. 展平多级双向链表

var endNode:Node?
    
    func flatten(_ head: Node?) -> Node? {
    
        if head == nil {
            return head
        }
        dfs(head)
        return head
    
    }
    
    func dfs(_ head:Node?){
        var tempHead = head
        var next : Node? = nil
        while tempHead != nil {
            //保存递归结束节点
            if(tempHead?.next == nil){
                endNode = tempHead
            }
            next = tempHead?.next
            if(tempHead?.child != nil){
                //当前节点和子节点相连
                let child = tempHead?.child
                tempHead?.next = child
                child?.prev = tempHead
                //将当前节点的子节点置空
                tempHead?.child = nil
                dfs(child)
                // 递归结束尾节点与下一节点相连
                if endNode != nil && next != nil {
                    endNode?.next = next
                    next?.prev = endNode
                }
            }
            
            tempHead = next
   
        }
    }