/**
* Definition for a Node.
* type Node struct {
* Val int
* Prev *Node
* Next *Node
* Child *Node
* }
*/
func LLTail(head *Node) *Node {
th := head
if th == nil {
return nil
}
for th.Next != nil {
th = th.Next
}
return th
}
func flatten(root *Node) *Node {
tn := root
for tn != nil {
if tn.Child != nil {
c := flatten(tn.Child)
ct := LLTail(c)
t := tn.Next
if t != nil {
t.Prev = ct
ct.Next = t
} else {
tn.Next = c
c.Prev = tn
}
tn.Next = c
c.Prev = tn
tn.Child = nil
} else {
tn = tn.Next
}
}
return root
}