給一串 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 傳給遞迴函數，取得該子串的頭尾，然後插入當前的位置與下一位置的中間。
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
