进入链表的遍历模块了

 

 

好复杂的题目描述。。。

DFS深度遍历+扁平拼接 

"""
# Definition for a Node.
class Node:def __init__(self, val, prev, next, child):self.val = valself.prev = prevself.next = nextself.child = child
"""class Solution:def flatten(self, head: 'Optional[Node]') -> 'Optional[Node]':#使用DFS遍历,返回child中最后一个结点def dfs(node):if not node:return#如果没有下一个结点并且没有child结点if not node.child and not node.next:return nodeelif node.child:#last表示child中最后一个结点last=dfs(node.child)#双链表的扁平化连接设置if last:last.next=node.nextif node.next:node.next.prev=last#node与child的扁平化连接设置node.next=node.childnode.child.prev=node#题目要求的子指针设置为空node.child=None#继续遍历last的childreturn dfs(last)#若结点有next无child，就继续查找next的childelse:return dfs(node.next)dfs(head)return head

 

ps:感谢Ben神，听一个老哥说可以用栈搞，估计不错，下次试试。