题目要求
You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list. Example:Input: 1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULLOutput:1-2-3-7-8-11-12-9-10-4-5-6-NULL思路一：递归实现深度优先遍历
从深度优先遍历的角度来看，每次遇到一个包含子节点中间双链表节点，就递归的调用展开方法将其展开，并将展开的结果插入到当前节点的后面。这里需要注意双链表前节点前后指针的变更。步骤如下：
Step1: 1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULLStep2:1---2---3---4---5---6--NULL | 7---8---11--12--9---10--NULL Step3:1---2---3---7---8---11--12--9---10--4---5---6--NULL 代码如下：
public Node flatten(Node head) { if(head == null) return head; Node tmp = head; while(tmp != null) { if(tmp.child != null) { Node child = flatten(tmp.child); tmp.child = null; Node next = tmp.next; tmp.next = child; child.prev = tmp; while(child.next != null) { child = child.next; } child.next = next; if(next != null) { next.prev = child; } tmp = next; }else { tmp = tmp.next; } } return head; }思路二：循环
上面的思路同样可以通过循环的方式来解决。每遇到一个有子节点的双链表节点，就将其子节点的头和尾拼接到父节点的双链表上，使其看上去是一个新的双链表。再对双链表的下一个节点进行判断。基本步骤如下：
Step1: 1---2---3---4---5---6--NULL | 7---8---9---10--NULL | 11--12--NULLStep2:1---2---3---7---8---9---10---4---5---6--NULL | 11--12--NULL Step3:1---2---3---7---8---11--12--9---10--4---5---6--NULL 代码如下：
public Node flatten(Node head) { if(head == null) return null; Node tmp = head; while(tmp != null) { if(tmp.child != null) { Node child = tmp.child; tmp.child = null; Node next = tmp.next; tmp.next = child; child.prev = tmp; while(child.next != null) { child = child.next; } if(next != null) { child.next = next; next.prev = child; } } tmp = tmp.next; } return head; }思路3：减少遍历次数
之前的两种思路，都会出现大量的重复遍历，重复遍历和叶子节点的深度成正相关，可以想方法将重复遍历的次数减少。其实，我们可以看见，无论我们何时将子节点展开，并拼接回父节点的双链表中，子节点展开的双链表的头结点是固定的，并且可以用父节点访问到。而尾节点必须通过重复遍历来查找并拼接。因此，如果每次都将展开后的尾节点返回，就可以无需重复遍历将展开的子节点拼接回父节点。代码如下：
public Node flatten(Node head) { flattenAndReturnTail(head); return head; } public Node flattenAndReturnTail(Node head) { if(head == null) return null; if(head.child == null) { if(head.next == null) return head; return flattenAndReturnTail(head.next); }else { Node child = head.child; head.child = null; Node next = head.next; Node childTail = flatten(child); head.next = child; child.prev = head; if(next != null) { childTail.next = next; next.prev = childTail; return flattenAndReturnTail(next); } return childTail; } }