fb 电面 展开层级链表

都是O(n)
第一种逐层

1->2->11->12
   |
   3->4->5
      |
      6->7
1-2-11-12->3-4-5->6-7

  static void flattenList(Node node) { 
          
        /*Base case*/
        if (node == null) { 
            return; 
        } 
          
        Node tmp = null; 
  
        /* Find tail node of first level linked list */
        Node tail = node; 
        while (tail.next != null) { 
            tail = tail.next; 
        } 
  
       
        // linked list till we reach the tail node 
        Node cur = node; 
        while (cur != tail) { 
  
            // If current node has a child 
            if (cur.child != null) { 
  
                // then append the child at the end of current list 
                tail.next = cur.child; 
  
                // and update the tail to new last node 
                tmp = cur.child; 
                while (tmp.next != null) { 
                    tmp = tmp.next; 
                } 
                tail = tmp; 
                cur.child = null;
            } 
  
            // Change current node 
            cur = cur.next; 
        } 
    } 
 

第二种中间插入，使用栈

1->2->11->12
   |
   3->4->5
      |
      6->7

1-2-3-4-6-7-5-11-12

static void flattenList(Node node) { 
    if (node == null) {
      return null;
    }
    Stack<Node> st = new Stack<>();
    Node cur = node;
    while (cur != null) {
      if (cur.child != null) {
        Node child = cur.child;
        cur.child = null;
        st.push(cur.next);
        cur.next = child;  
      } 
      if (cur.next == null && !st.isEmpty()) {
        cur.next = st.pop();
      }
      cur = cur.next;
    }  
  }