430-扁平化多级双向链表.md

#430. 扁平化多级双向链表

您将获得一个双向链表，除了下一个和前一个指针之外，它还有一个子指针，可能指向单独的双向链表。这些子列表可能有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

扁平化列表，使所有结点出现在单级双链表中。您将获得列表第一级的头部。

示例:

输入:
 1---2---3---4---5---6--NULL
         |
         7---8---9---10--NULL
             |
             11--12--NULL

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

以上示例的说明:

给出以下多级双向链表:

我们应该返回如下所示的扁平双向链表:

思路

一：

常规思路：

1. 从头遍历链表，依次找到有子节点的节点 n；

2. 将 n 的子节点对应的双向链表接入第一层链表中，再接续遍历后续节点；

3. 依次遍历，直到最后节点。

二：

节约二级、三级链表的重复遍历时间（同事助攻补充）：

1. 递归遍历；

2. 利用遍历到的节点n，创建新节点；

3. 对节点的子节点和 next 节点依次递归；

4. 重新生成一个新链表，依次添加创建的新节点。

解决

思路一对应 code：

/*
// Definition for a Node.
class Node {
public:
    int val = NULL;
    Node* prev = NULL;
    Node* next = NULL;
    Node* child = NULL;

    Node() {}

    Node(int _val, Node* _prev, Node* _next, Node* _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
public:
    Node* flatten(Node* head) {
        if(head == nullptr) {
			return nullptr;
		}
		
		for(Node* p = head; p != nullptr; p = p->next) {
			Node* n = p->next;
			
			if(p->child != nullptr) {
				Node* c = p->child;
				p->next = c;
				c->prev = p;
				p->child = nullptr;
				
				while(c && c->next) {
					c = c->next;
				}
				c->next = n;
				if(n) {
					n->prev = c;
				}
			}
		}
		return head;
    }
};

思路二对应 code：

/*
// Definition for a Node.
class Node {
    public int val;
    public Node prev;
    public Node next;
    public Node child;

    public Node() {}

    public Node(int _val,Node _prev,Node _next,Node _child) {
        val = _val;
        prev = _prev;
        next = _next;
        child = _child;
    }
};
*/
class Solution {
    
    Node result,end;
    
    public Node flatten(Node head) {
        fun(head);
        return result;
    }
    
    private void fun(Node node){
        if(node == null) return;
        Node newNode = new Node(node.val,end,node.next,null);
        if(end != null)
            end.next = newNode;
        end = newNode;
        
        if(result == null) result = newNode;
        
        if(node.child != null){
            fun(node.child);
        }
        
        fun(node.next);
    } 
}