LCR 028
题目：LCR 028
解法一：深度优先搜索
遍历链表，若某节点存在子链，则遍历子链，遍历完后，返回子链最后一个节点 last，将 last 与当前链表的 next 相连
public Node flatten(Node head) {dfs(head);return head;}public Node dfs(Node head) {Node cur = head, last = null, next = null;while (cur != null) {last = cur;next = cur.next;//连接孩子节点，更新last，并把last和next相连if (cur.child != null) {//连接childcur.next = cur.child;cur.child.prev = cur;//获取子链尾节点last = dfs(cur.child);//将子节点置空cur.child = null;//将子链尾节点和下一个节点相连last.next = next;if (next != null) next.prev = last;}//此处不能用cur=cur.next，因为此时cur的next已经被修改为孩子节点cur = next;}return last;}
注意：
-
当
next为空时，只需要将last的next指针指向next，不需要将next的prev指针指向last -
扁平化子链后，需要将
child节点置空，否则测试不通过