# 430 Flatten a Multilevel Doubly Linked List

Flatten a Multilevel Doubly Linked List

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--NULL

Output:
1-2-3-7-8-11-12-9-10-4-5-6-NULL

題問敘述如上，是要將一個Double listed 壓平，這裡我的解法是用遞迴，是先將

root = head ，在com(head)，跑到root =3 時，找到child 7

將node 3 的next = node 7;

node 7 的prev = node 3;

將node 3 的child = null;

1---2---3
        |
        7---8 ---n
　　　   ↑
    　root.child

root ==> 1-2-3-NULL， temp ==> 4-5-6-null

此時用root.child (7) 再備代入com方法(7)，此時root就是7開始跑

com()方法裡 計算未跑為4-5-6-null，所以con ==> 4-5-6-NULL

 4---5---6--NULL

-----------------------------------------------------------------------------------------------------------------------------------

root = 7 ，在com(head)，跑到root =8 時，找到child 11

將node 8 的next = node 11;

node 11 的prev = node 8;

將node 8 的child = null;

1---2---3
        |

1---2---3
         |
         7---8
             |
             11
             ↑
         root.child
             

root ==> 1-2-3-7-8-NULL， temp ==> 9-10-null

此時用root.child (11) 再備代入com方法(11)，此時root就是11開始跑

com()方法裡 計算未跑為9-10-null，所以新的con ==> 9-10-4-5-6-NULL

  目前con ==> -4---5---6--NULL
         
  現在未跑   9---10--NULL
             |
  新的con ==> 9-10-4---5---6--NULL      

-------------------------------------------------------------------------------------------------------------

跑完迴圈，root = 1-2-3-7-8-11-12-null

1---2---3
         |
         7---8
             |
             11--12--NULL

此時跑完迴圈con 目前是con ==> 9-10-4-5-6-NULL

root = con;

con = null; //這裡一定要清con，不然會一直無限while。

此時root ==> 9-10-4-5-6-NULL

代入com方法

root如下

 1---2---3            4---5---6--NULL
         |            ↑
         7---8    9---10
             |    ↑
             11--12